- 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.
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