can you explain an algorithm used to solve this problem without coding it: You a

Q: can you explain an algorithm used to solve this problem without coding it: You a

Solution 1: Simple but not efficient: Use two loops- Steps: (1): Run a loop on given price array , from i=0 to n-1 (2) -----go inside the loop and declare count=0; (3)-----Run another loop inside first loop,like while(j>=0 && price[j]

ID: 3734934 • Letter: C

Question

can you explain an algorithm used to solve this problem without coding it:

You are given an array a1...an of stock prices of a commodity on each day, i.e., ai is the price of the stock on day i. The span of a stock price on day i is the number of consecutive days before day i for which the price of the stock is less than or equal to ai. You may assume that the price of the stock on day 0 is o, so that the span of the stock on day 1 is 0. For example, if the prices were [7,2,4,6,8,5,6], then the span of the stock on day 4 is 2 as there are two consecutive days (days 2 and 3) in which the prices were less than or equal to the price of the stock on day 4 (which is 6). As other examples, the span of the stock on day 5 is 4, and day 7 is 1. Please design and analyze an algorithm that computes the span of the stock on each day. So the output is an array (say b), where bi is the span of the stock on day i. For full credit, your algorithm should run as fast as possible

Explanation / Answer

Solution 1: Simple but not efficient: Use two loops-

Steps:

(1): Run a loop on given price array , from i=0 to n-1

(2) -----go inside the loop and declare count=0;

(3)-----Run another loop inside first loop,like while(j>=0 && price[j]<=price[i]) means from j=i-1 to 0

(4)---------increment count inside second loop

(5)----Now assigne value of count to spam[i]=count

Algorithm:

calculateSpan(int price[], int n, int spam[])

(1) for i<-0 to n-1 {

(2)count=0,j=i-1

(3)while(j>=0 and price[j]<=price[i]){

(4) count++

(5) }

(6) span[i]=count

(7) }

Analysis:

Time complexity: O(N*N) if N is length of prices array

Space Complexity: O(1), No extra array used

*****************************************************************************

Solution 2: Efficient using Stack. -

steps:

(1) declare empty stack , stack will store indexes of prices

(2) Traverse the price array

(3)----Remove elements from stack till price[stack[top]]<=price[i] or stack.empty() means remove till top of stack is smaller than current price

(4)----If stack is empty means all left element are smaller than current element

(5)--------span[i]=i

(6)----else

(7)--------span[i]=i-stack.top()

(8)---stack.push(i)

Algorithm: This algorithm using stack

//I wrote with brackets so you can understand it clearly

void calculateSpan(int prices[], int n, int span[])

{

// Creata a stack

stack

//push index of first element

stack.push(0);

// Span value of first element is always 0

span[0] = 0;

// Calculate span values for rest of the elements

for (int i = 1; i < n; i++)

{

// Pop elements from stack while stack is not empty and top of

// stack is smaller than price[i]

while (!stack.empty() && price[stack.top()] <= price[i])

{

stack.pop();

}

if(stack.isEmpty())

{

span[i]=i;

}

else

{

span[i]=i-stack.top();

}

// Push this element to stack

sttack.push(i);

}

Analysis:

Time complexity: O(N) if N is length of prices array

Space Complexity: O(N), Size of stack

Navigate

can you exaplin why it\'s b & not a. MULTIPLE CHOICES. There is one best answer

can you explain how to arrive at answer as well. i found a similar question on h

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

can you explain an algorithm used to solve this problem without coding it: You a

Question

Explanation / Answer

Related Questions

Navigate