Find Number of sub-arrays having sum exactly equal to k in C++

In this tutorial, we will learn how to find the number of sub-arrays with a sum exactly equal to a given number in C++.

We will not be discussing how to find one such sub array given an array. Our motive is to find the number of such sub-arrays that exist. The approaches may be similar for both problems but with changes of course.

The code that we discuss here will be able to handle negative numbers as well.

Number of sub-arrays with a given sum in C++

The problem:

Input: You will be given an array and a target sum. Our motive is to find the number of contiguous sub arrays, each when summed up individually give the target sum.

Example:

Input:

-3 2 -3 -4 3
-1

Output must be 3. The sub-arrays are (-3, 2), (2, -3), (-4, 3).

Naive approach:

A common approach would be to look at every possible combination of contiguous arrays possible and figure out if their sum is the target sum. This would require us to fix an element and go through every other element which will heavily cost us O(n^2).

Efficient approach:

We iterate through the array once and as we go through it, we sum the elements up to that index and store the total sum until that index and the number of times they occurred in an unordered map as key and value. At each iteration, we check if the Current total sum is equal to the given sum which will make us update our number of sub arrays by one. We check if the current sum minus the target sum is present in the unordered map. If it is present we update our number of sub arrays by the number of times that sum appears in the unordered map. This map lookup costs us O(1) and hence doesn’t affect our time complexity.

At line 13, we check if the element is present in the unordered map or not. If it isn’t present it returns an iterator to the end and we skip the check.

Line 15 is the case when the lookup is successful.

Code:

#include <stdio.h>
using namespace std; 
#include <iostream>
#include <unordered_map>
int noSubArrays(int array[], int n, int targetSum){
    int currentSum=0, result=0;
    unordered_map<int, int>sumLog;
    for(int i=0; i<n; i++){
        currentSum += array[i];
        if(currentSum==targetSum)
            result+=1;
        int difference = currentSum - targetSum;
        if(sumLog.find(difference) == sumLog.end())
            goto endoffor;
        else
            result+=(sumLog[difference]);
        endoffor: 
        sumLog[currentSum]+=1;
      
    }
 
    return result;   
}

int main(){
    
    int n, targetSum;
    cout<<"Enter the number of elements"<<endl;
    cin>>n;
    cout<<"Enter the target sum"<<endl;
    cin>>targetSum;
    int array[n];
    cout<<"Enter the elements"<<endl;
    for(int i=0; i<n; i++){
        int ele;
        cin>>ele;
        array[i]=ele;
    }
    int result=noSubArrays(array, n, targetSum);
    if(targetSum==0)
    result++; //This is to include the case of singleton set with no elements
    cout<<"The number of Sub arrays with sum "<< targetSum <<" is "<<result;

    return 0;
}

Output:

Enter the number of elements                                                                          

5                                                                                                     

Enter the target sum                                                                                  

-1                                                                                                    

Enter the elements                                                                                    

-3 2 -3 -4 3                                                                                          

The number of Sub arrays with sum -1 is 3

Also read: Sorting ugly numbers in an array at their relative positions in C++