- Write a program to find a sub array whose sum is S.

Given an integer array of size N and an integer S. We have to **find a subarray whose sum is S**. There may be multiple subarrays whose sum is S but we have to print only the first subarray.

For Example :

Input Array : 3 5 7 12 1 9 10 4 6 2 S = 32 Sub Array is from 3 to 6 index Input Array : 3 5 7 12 1 9 10 4 6 2 S = 38 No Sub Array of sum 38

Let inputArray be an integer array of size N and we want to find a continuous subarray whose sum is equal to S.

**Brute Force Method : O(n**

^{2})- Using two for loops, generate all possible subarrays of inputArray and check if it's sum is equal to S.
- Outer for loop will fix the first element of subarray(let it be A) and inner for loop will find the sum of all subarrays starting from A.

^{2})

## C program to find a sub array whose sum is equal to given number.

#include<stdio.h> void printSubArraySum(int *array, int size, int sum) { int i, j, currentSum; /* For every element array[i], find the sum of all sub arrays starting from array[i] and compare it with sum */ for (i = 0; i < size; i++) { currentSum=0; for (j = i; j < size; j++) { currentSum += array[j]; if(currentSum == sum) { /* sub Array found */ printf("Sub Array is from %d to %d index\n", i, j); return; } } } printf("No Sub Array of sum %d", sum); } int main() { int array[10] = {3, 5, 7, 12, 1, 9, 10, 4, 6, 2}; /* Find a sub array of sum 32 */ printSubArraySum(array, 10, 32); /* Find a sub array of sum 37 */ printSubArraySum(array, 10, 38); return 0; }Output

Sub Array is from 3 to 6 index No Sub Array of sum 38

**Optimized solution : O(n)**

- Initialize left, right and currentSum to 0. left and right index marks the boundary indexes of current subarray.
- Traverse inputArray using right index and find the sum of current subarray(from index left to right).
- If currentSum is equal to S, then we found a subarray with sum S.
- If currentSum > S, then keep on reducing the size of subarray by incrementing left index until sum of array becomes <= S.

#include<stdio.h> void printSubArraySum(int *array, int size, int sum) { int left, right, currentSum; left = right = 0; currentSum = 0; for (right = 0; right < size; right++) { currentSum += array[right]; if(currentSum >= sum){ while(currentSum > sum){ currentSum -= array[left]; left++; } } if(currentSum == sum) { /* sub Array found */ printf("Sub Array is from %d to %d index\n", left, right); return; } } printf("No Sub Array of sum %d\n", sum); } int main() { int array[10] = {3, 5, 7, 12, 1, 9, 10, 4, 6, 2}; /* Find a sub array of sum 32 */ printSubArraySum(array, 10, 32); /* Find a sub array of sum 37 */ printSubArraySum(array, 10, 38); return 0; }Output

Sub Array is from 3 to 6 index No Sub Array of sum 38