GATE CSE 1997 | Question: 17

Question

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.

Comments

I think this question is same as " smallest subarray with a sum  greater than a given value " .

 

 

---

Thanks. It’s Helpful.

Answer 1

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.

Comments

@Ayush Upadhyaya

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??

---

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

---

To visualize the above algorithm, think of a worm: it moves the head (front portion of the body) first, then once it stretched its entire body it moves it back half of the body.

Here the analogy is: moving front part of the body – incrementing j

Stopping once the entire body is stretched – stopping once the sum is greater than the given value

moving the back part of the body – incrementing i (here we store the min value, and continue for the rest of the elements to find the overall minimum)

Answer 2

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)

Comments

for(i:=10;i<n-1;i++)do{

for(j=1;j<n-1;j++)do

{

if a[i]+a[j]==a

do{

print i,j

}end

}end

}end

---

Time complex - Exponential O(2^n) for above approch , which is worst