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.


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).


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

Efficient Code-


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).



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];
// 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,055 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>