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-

[cpp]

//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
[/cpp]

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-

[cpp]
{
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
}

[/cpp]

Leave a Comment

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