# 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 + arr + arr + ... 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 = 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;
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]