Sub-array with given sum code in c++.

Given an array A which contains both positive and negative integers and a value of sum k.We have to find the subarray which contains the sum equal to that sum k.

INPUT:-

Input array be: [1, 3, 7, 9, 11, 15, 8, 6]

Sum = 20
Output will be: 0 and 3 → [1, 3, 7, 9], subarray sum = 20
Input : arr[] = {2, 4, 8}, Sum = 10
Output : -1.(because we can’t achieve target sum by any continuous subarray)

Readers are requested to try the question before approaching towards the solution. They can submit their codes in comment section below.

METHOD 1:- Naive Approach

Consider all sub-arrays  calculate their sum and if the sum of sub-array equals the given sum then print the sub array.

code:-

[code language=”cpp”]

#include <stdio.h>

// Utility function to print the sub-array arr[i,j]
void print(int arr[], int i, int j)
{
printf("[%d..%d] — { ", i, j);
for (int k = i; k <= j; k++) {
printf("%d ", arr[k]);
}
printf("}\n");
}

// Function to find sub-arrays with given sum in an array
void findSubarrays(int arr[], int n, int sum)
{
for (int i = 0; i < n; i++)
{
int sum_so_far = 0;

// consider all sub-arrays starting from i and ending at j
for (int j = i; j < n; j++)
{
// sum of elements so far
sum_so_far += arr[j];

// if sum so far is equal to the given sum
if (sum_so_far == sum) {
print(arr, i, j);
}
}
}
}

// main function
int main()
{
int arr[] = { 3, 4, -7, 1, 3, 3, 1, -4 };
int sum = 7;

int n = sizeof(arr)/sizeof(arr[0]);
findSubarrays(arr, n, sum);

return 0;
}

[/code]

The complexity using this approach is O(n*n).

Method 2:-

In order to reduce the time complexity from O(n*n) to O(n) we can use the sliding window approach .

The algorithm for this approach is as follows:-

1.Create a subarray sum function which takes the array and sum as argument and gives start and end indexes of the subarray with given sum.

2.First Initialize current_sum as first element of the array and store start index as 0.
If current_sum exceeds sum, remove staring element and increment start index.
If current_sum equals to sum then return the start and end indexes.
3.Add elements to the current_sum one by one.
If loop ends then print “No subarray found with given sum

 

Code:-

[code language=”cpp”]

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

int SubarrySum(int array[], int n, int sum)
{
//Initialize current_sum = first element.Therefore, start_index =0
int current_sum = array[0];
int start_index = 0;

//if current_sum > sum remove last element
for(int i = 1; i <= n; i++)
{
while(current_sum > sum && start_index < i-1)
{
current_sum = current_sum – array[start_index];
start_index++;
}
if(current_sum == sum)
{
cout<<"Subarray with given sum is between indexes "<<start_index<<" and "<<i-1<<endl;
return 1;
}
//Add current element to current_sum
if(i < n)
{
current_sum = current_sum + array[i];
}
}
cout<<"No subarray found with given sum"<<endl;
return 0;
}

//Main function
int main()
{
int input_array[] = {1,3, 8, 9,11, 13, 17, 21};
int N = sizeof(input_array)/sizeof(input_array[0]);
int Sum = 28;
SubarrySum(input_array,N,Sum);
return 0;
}

[/code]

 

The run time complexity for this approach is  O(n).