  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Finding SubArray with Given Sum In this article, we are going to discuss a very famous question from an interview perspective called subarray with given sum.

## How to Find SubArray with Given Sum:

This problem is also known as subarray sum equals k. Given an array of non-negative integers and an integer sum, find a subarray that adds to a given sum.

Note: There may be more than one subarray with sum as the given sum, print first such subarray.

Examples:

``Input: arr[] = [ 1, 20, 3, 10, 5 ], sum = 33`` Output:

``Sum found between indexes 1 and 3``

Explanation:
Sum of elements between indices 1 and 3 is 20 + 3 + 10 = 33

Input:

``arr[] = [1, 4, 0, 0, 3, 10, 5], sum = 7``

Output:

``Sum found between indexes 1 and 4``

Explanation:
Sum of elements between indices 1 and 4 is 4 + 0 + 0 + 3 = 7

Input:

``arr[] = [ 1, 4 ], sum = 0``

Output:

``No subarray found``

Explanation:
There is no subarray with 0 sum

### Approach 1 to Find SubArray with Given Sum

Find subarray with given sum using Nested loop
The idea behind this approach is to consider all subarrays of the given array one by one and check the sum of every subarray.

Algorithm:
Run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from j.

Follow the steps given below to implement the approach:

• Traverse the array from start to end.
• From every index start another loop from i to the end of the array to get all subarrays starting from i, and keep a variable currentSum to calculate the sum of every subarray.
• For every index in inner loop update currentSum = currentSum + arr[j]
• If the currentSum is equal to the given sum then print the subarray.

Below is the implementation of the above approach.

```#include <bits/stdc++.h>
using namespace std;

/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
void subArraySum(int arr[], int n, int sum)
{

// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];

if (currentSum == sum) {
cout << "Sum found at indexes " << i << endl;
return;
}
else {
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];

if (currentSum == sum) {
cout << "Sum found between indexes "
<< i << " and " << j << endl;
return;
}
}
}
}
cout << "No subarray found";
return;
}

// Driver Code
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
```

Output:

``Sum found between indexes 1 and 4``

Time Complexity: O(N2), Trying all subarrays from every index, used nested loop for the same

Auxiliary Space: O(1).

### Approach 2 to Find SubArray With Given Sum

Find subarray with given sum using sliding window technique
The idea is simple as we know that all the elements in subarray are positive so, If a subarray has sum greater than the given sum then there is no possibility that adding elements to the current subarray will be equal to the given sum. So the Idea is to use a similar approach to a sliding window technique.

Algorithm:
Step 2: add elements to the subarray until the sum is less than x( given sum ).
Step 3: If the sum is greater than x, remove elements from the start of the current subarray.

Follow the steps given below to implement the approach:

• Create two variables, start=0, currentSum = arr
• Traverse the array from index 1 to end.
• Update the variable currentSum by adding current element, currentSum = currentSum + arr[i]
• If the currentSum is greater than the given sum, update the variable currentSum as currentSum = currentSum – arr[start],
and update start as, start++.
• If the currentSum is equal to given sum, print the subarray and break the loop.

Below is the implementation of the above approach.

### Subarray with given sum 2

```#include <iostream>
using namespace std;

/* Returns true if the there is a subarray of
arr[] with a sum equal to 'sum' otherwise
returns false. Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
/* Initialize currentSum as value of
first element and starting point as 0 */
int currentSum = arr, start = 0, i;

/* Add elements one by one to currentSum and
if the currentSum exceeds the sum,
then remove starting element */
for (i = 1; i <= n; i++) {
// If currentSum exceeds the sum,
// then remove the starting elements
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}

// If currentSum becomes equal to sum,
// then return true
if (currentSum == sum) {
cout << "Sum found between indexes " << start
<< " and " << i - 1;
return 1;
}

// Add this element to currentSum
if (i < n)
currentSum = currentSum + arr[i];
}

// If we reach here, then no subarray
cout << "No subarray found";
return 0;
}

// Driver Code
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
```

Output:

``Sum found between indexes 1 and 4``

Time Complexity: O(N)
Auxiliary Space: O(1). Since no extra space has been taken.

Finally, we optimized our code and reduced our time complexity from O(N2) to O(N).