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; }