edited by
4,965 views
28 votes
28 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.
edited by

2 Answers

Best answer
27 votes
27 votes
begin
i:=1;j:=1;
sum := A[1]
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.

edited by
3 votes
3 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)

Related questions

45 votes
45 votes
6 answers
4
Kathleen asked Sep 29, 2014
8,800 views
Let $G$ be the graph with $100$ vertices numbered $1$ to $100$. Two vertices $i$ and $j$ are adjacent if $\vert i-j \vert =8$ or $\vert i-j \vert=12$. The number of con...