# Program to find SubArray Whose Sum is Equal to Given Number

• 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(n2)
• 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.
Time Complexity : O(n2)

## 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 = {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.
Time Complexity : O(n)
```#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 = {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
```