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[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.
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[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
Posted by
Labels: ,