No of subarrays with sum K

Given an array arr of n integers, print the no of subarrays with sum k in it.

Example Test Cases

Sample Test Case 1

Input Array: [1, 2, 3]
K: 5
Expected Output: 1
Explanation: The only subarray with sum 5 is [2, 3] . Therefore, the answer is 1 .

Input Array: [1, 2, 3, -5, 4, 1]
K: 5 Expected Output: 4
Explanation: The 4 subarrays with sum 5 are :

• [2, 3]
• [4, 1]
• [2, 3, -5, 4, 1]
• [1, 2, 3, -5, 4]

Solution

Let us define cu[i] = arr[0] + arr[1] + arr[2] + ... arr[i] (cumulative sum).
If the sum of subarray b/w index i + 1 and j is equal to k , then cu[j] - cu[i] = k .
Therefore, the no of ways in which we can make a subarray of sum k ending at index j , will be equal to the number of indexes which have cumulative sum = cu[j] - k .
Since j can go from 0 to n -1 , we will sum up the above calculated count for all possible values of j and that will be our answer. We can easily implement the above algorithm using a hash table as shown below.

Implementation

 
#include <bits/stdc++.h>
using namespace std;

int findCount(vector& arr, int k) {
    // Hash table to store the frequency of each cumulative sum

    unordered_map mp;
    int n = arr.size();

    // Running cumulative sum
    int total = 0;
    // cnt stores the count of subarrays with K sum.
    int cnt = 0;

    // This is because there is at least one way to make cumulative sum 0 (by not including any element within the subarray).
    mp[0] = 1;

    for(int j = 0; j < n; j++) {
        total += arr[j];
        if (mp[total - k] != 0) {
            cnt += mp[total - k];
        }
        mp[total]++;
    }
    return cnt;
}
int main() {
    vector arr = { 1, 2, 3, -5, 2, 3 };
    int k = 5;
    cout << "No of subarrays with sum " << k << " are " << findCount(arr, k) << "\n";
    return 0;
}