Sub-array with given sum in C

November 1, 2021

Sub-array with given sum

Here, in this page we will write the program for sub-array with given sum in C.Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Subarrays having their sum equal to the given integer.
Example : arr[ ] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output:
Sum found between indexes 1 and 4 Sum of elements between indices 1 and 4 is (4 + 0 + 0 + 3) = 7

Algorithm :

Traverse the array from start to end.
From every index start another loop from i to the end of array to get all sub-array starting from i, keep a variable sum to calculate the sum.
For every index in inner loop update sum = sum + a[j]
If the sum is equal to the given sum then print the sub-array.

Code in C based on above Algorithm

#include<stdio.h>

int ArraySubSum(int a[], int n, int sum){
    
    int currsum, i, j; 

    for (i = 0; i < n; i++) { 
    currsum = a[i]; 

            
    for (j = i + 1; j <= n; j++) { 
    
    if (currsum == sum) { 
        int p = j-1; 
        printf("Sum found between indexes %d and %d ", i , p); 
        return 1; 
    } 

    if (currsum > sum || j == n) 
    break; 
    
    currsum = currsum + a[j]; 
    } 
} 
printf("No subarray found"); 
return 0;
}


int main(){ 
    
    int n=7;  
    int arr[] = {1, 4, 0, 0, 3, 10, 5}; 
        
    int sum = 7; 
    ArraySubSum(arr, n, sum); 
    return 0;
     
}

Output :


Sum found between indexes 1 and 4