The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
808 views

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.
asked in DS by Veteran (59.6k points)
edited by | 808 views

2 Answers

+13 votes
Best answer
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.

answered by Active (4.7k 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 (2.3k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,685 questions
48,650 answers
156,447 comments
63,961 users