Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 20 Apr, 2021

Moderate

```
Input: ‘N’ = 4, ‘arr’ = [3, 1, 2, 4], 'K' = 6
Output: 2
Explanation: The subarrays that sum up to '6' are: [3, 1, 2], and [2, 4].
```

```
The first input line contains a single integer ‘T’, denoting the number of test cases.
For each Test case:
The first line of each test case input contains two space-separated integers, where the first integer represents the length of the array 'N', and the second integer is the value ‘K’.
The next line of each test contains ‘N’ space-separated integers, which are the elements of the ‘arr’ array.
```

```
For every test case, return the count of all subarrays that sum up to the integer 'K'.
```

```
You do not need to print anything; it has already been taken care of. Just Implement the given function.
```

```
1 <= T <= 10
1 <= N<= 10^3
1 <= arr[i] <= 10^9
1 <= K <= 10^9
Time Limit: 1 sec
```

A simple solution could be to traverse all the subarrays and calculate their sum. If the sum is equal to the given required sum, then increment the count of subarrays. Finally, return the count of such subarrays.

**// **Function to find the number of subarrays with sum ‘k’

**function **findAllSubarraysWithGivenSum**(int[] arr, int k):**

**Int ‘n’ be the size of the array ‘arr’.****Initialize a variable ‘res’ initially assigned to ‘0’, which will store the number of subarrays with sum ‘k’.****Iterate from index ‘1’ to index ‘n’ using variable ‘i’:**- Initialize a variable ‘currSum’ initially assigned to ‘0’, which will store the sum of the current subarray.
- Iterate from index ‘i’ to index ‘n’ using variable ‘j’:
- Add arr[j] to ‘currSum’.
- If ‘currSum == k’:
- Increment ‘res’ by 1.

- Else if ‘currSum > k’:
- Break

**Return ‘res’.**

An efficient solution is while traversing the array, we keep storing the sum that we have gotten so far in ‘currSum’. Here, we would also need to maintain the count of different values of ‘currSum’ in a hashmap. Now, if the value of ‘currSum’ equals the desired sum at any instance, we increment the count of subarrays by one.

While if, the value of ‘currSum’ exceeds the desired sum by a value (‘currSum’ - ‘k’), then if this value is removed from ‘currSum’, the desired sum can be obtained. From the map, find the number of subarrays previously found having a sum equal to (‘currSum’ - ‘k’). Excluding all those subarrays from the current subarray gives new subarrays having the desired sum.

**function **findAllSubarraysWithGivenSum**(int[] arr, int k):**

**Int ‘n’ be the size of the array ‘arr’.****Initialize a variable ‘currSum’ initially assigned to ‘0’, which will store the sum of the current subarray on which we are iterating.****Initialise a variable ‘res’ initially assigned to ‘0’, which will store the number of subarrays with sum ‘k’.****Initialise a hashmap ‘prevSum’, which will store all the counts of subarrays having a sum equal to a particular ‘currSum’ we have created.****Iterate from index ‘1’ to ‘n’ using variable ‘i’:**- Add arr[i] to ‘currSum’.
- If ‘currSum == k’:
- Increment ‘res’ by 1.

- If ‘currSum - k’ exists in ‘prevSum’:
- Add ‘prevSum[currSum - k]’ to ‘res’.

- Increment ‘prevSum[currSum]’ by 1.

**Return ‘res’.**