+12 votes
943 views

An array $A$ contains $n \geq 1$ positive integers in the locations $A, A, \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.

asked in DS
edited | 943 views

## 2 Answers

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

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.

answered by Active (4.9k points)
edited by
0
can you explain the algorithm?
0
Can you please explain why do we have to strip off the first element at the end of the algorithm?
+1
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
Someone pleasetake an example of any array and run the code. I am finding some trouble in it.
+1
0 votes
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)
answered by Active (4.4k points)

+26 votes
4 answers
4
+22 votes
4 answers
5
+20 votes
2 answers
6