The Gateway to Computer Science Excellence

+15 votes

An array $A$ contains $n \geq 1$ positive integers in the locations $A[1], A[2], \dots A[n]$. The following program fragment prints the length of a shortest sequence of consecutive elements of $A$, $A[i], A[i+1], \dots,A[j]$ such that the sum of their values is $\geq M$, a given positive number. It prints ‘$n+1$’ if no such sequence exists. Complete the program by filling in the boxes. In each case use the simplest possible expression. Write only the line number and the contents of the box.

begin i:=1;j:=1; sum := ◻ min:=n; finish:=false; while not finish do if ◻ then if j=n then finish:=true else begin j:=j+1; sum:= ◻ end else begin if(j-i) < min then min:=j-i; sum:=sum –A[i]; i:=i+1; end writeln (min +1); end.

+16 votes

Best answer

begin i:=1;j:=1; sum :=min:=n; finish:=false; while not finish do ifA[1]then if j=n then finish:=true else begin j:=j+1; sum:=sum < Mend else begin if(j-i) < min then min:=j-i; sum:=sum – A[i]; i:=i+1; end writeln (min +1); end.sum + A[j]

**Algorithm**

*'i' indicates the starting marker and 'j' acts as ending marker for the sum sequence. 'sum' is initialised as the first element in the array because the algorithm proceeds by taking the sum of remaining elements. 'finish' is a boolean variable that indicates exit from the loop.*

After entering the loop for the first time with '$finish$' as false, the sum is checked if it's strictly less than "$M$". If that's the case j is incremented and the sum is modified to sum $+ A[j]$. When 'sum' becomes greater than or equal to '$M$', '$min$' is modified to the latest number of elements that make the sum greater than or equal to '$M$' and then, the first element is stripped off from the sum and '$i$' is incremented by one to move the initial marker of the sum sequence. The loop runs till '$j$' reaches the end of the array.

The algorithm keeps track of '$min$' i.e. the number of elements in the minimum sum sequence. This is very similar to the way we find the minimum value in an array by modifying the min value whenever a lesser value is encountered.

+2

Bcoz we are trying to find the minimum sequence. It is possible that sum of 3 elems is greater or equal than M, but even if we take last 2 elems of the 3 elems we may get sum greater or equal to M.

0

What if we with take last 2 elements of those 3 elements and then we are not getting the sum >= M ???

0

@Roshan Here we are checking if there exists a sequence which is even smaller than the one which we have already found. And according to your query, if for the last two elements we get sum <M, then that won't be a problem because we already have length of smallest sequence that make a sum of >=M in a variable called min

0

Here we r doing like this

How many minimum consecutive number are there whose sum greater than $200$??

So, answer $3.$

because numbers are $20, 90,100$

right??

0

A better way to understand this :

1. Keep on reading the numbers, adding them to sum until it crosses the threshold,

2. keep on decreasing the value until it reaches less than the given threshold, remember that 'min' value in the variable, again starting step1 and only modifing the min variable , if we come across a lesser length sequence

1. Keep on reading the numbers, adding them to sum until it crosses the threshold,

2. keep on decreasing the value until it reaches less than the given threshold, remember that 'min' value in the variable, again starting step1 and only modifing the min variable , if we come across a lesser length sequence

+1 vote

Although answer is correct , I just want to mentioned another algorithm that came to my mind. I am just writing algorithm and not speudo code at it will be bit time consuming

Alternative algorithm

first take individual element and check if any of element is >= M . If u find any such element answer will be 1.

then check for all pair of two consecutive element. If you find any such pair whose sum id >= M then answer is 2

then check for all pair of three consecutive element. If you find any such triplet whose sum id >= M then answer is 3

this goes on till length crosses n.

If no such sequence found return n+1 (as said in question)

Alternative algorithm

first take individual element and check if any of element is >= M . If u find any such element answer will be 1.

then check for all pair of two consecutive element. If you find any such pair whose sum id >= M then answer is 2

then check for all pair of three consecutive element. If you find any such triplet whose sum id >= M then answer is 3

this goes on till length crosses n.

If no such sequence found return n+1 (as said in question)

52,217 questions

59,907 answers

201,103 comments

118,146 users