Subarray with given sum

Given a list of integers,our task is to find if a sub-sequence which adds to a given number exists or not.

Example-

The given list is (1,4,20,5,5) and the given number or sum is 29.
Then,the sub-sequence which adds to 29 is (4,20,5).

Brute Force-

All the sub-sequences are considered and its sum is compared with the given value.Its time complexity is O(N^2).

Code-


//arr[0...N-1] contains the given integers
// and the given number is X.
for(i=0;i<N;i++)
{
s=arr[i];
for(j=i+1;j<N;j++)
{
    s=s+arr[j];
    if(s==X) return 1;  // sub array found
}
}
return 0;   //sub-array not found

Efficient Code-

Algorithm-

1. Initialize a variable curr_sum as first element.
2. Start from the second element and add all elements one by one to the curr_sum.
3. If curr_sum becomes equal to X, then a sub-sequence/sub-array is found.
4. If curr_sum exceeds X, then remove trailing elements one by one until curr_sum is less than X.

Its time complexity is O(N).

Code-

{
curr_sum=arr[0];
start=0;

for (i = 1; i <= n; i++)
    {
 // If curr_sum exceeds X, then 
 // remove the starting elements

        while (curr_sum > X && start < i-1)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }
 
// If curr_sum becomes equal to X, 
// then return true

        if (curr_sum == X)
        {
            return 1;    //sub-array found
        }
 
        // Add this element to curr_sum

        if (i < n)
          curr_sum = curr_sum + arr[i];
    }
return 0;  //sub-array not found
}
 

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

41,728 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>