Count All Subarrays With Given Sum

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
206 upvotes
Asked in companies
SAP LabsCognizantCultfit

Problem statement

You are given an integer array 'arr' of size 'N' and an integer 'K'.

Your task is to find the total number of subarrays of the given array whose sum of elements is equal to k.

A subarray is defined as a contiguous block of elements in the array.

Example: 
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].
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
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.
Output Format: 
For every test case, return the count of all subarrays that sum up to the integer 'K'.
Note: 
You do not need to print anything; it has already been taken care of. Just Implement the given function.
Constraint : 
1 <= T <= 10
1 <= N<= 10^3
1 <= arr[i] <= 10^9
1 <= K <= 10^9

Time Limit: 1 sec
Sample Input 1:
2
4 6
3 1 2 4

3 3
1 2 3
Sample output 1:
2
2
Explanation:
Test Case 1:

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].

Test Case 2:

Input: ‘N’ = 3, ‘arr’ = [1, 2, 3], 'K' = 3

Output: 2

Explanation: The subarrays that sum up to '7' are: [1, 2], and [3].
Sample Input 2:
2
3 7
1 2 3

4 9
6 3 5 2
Sample output 2:
0
1
Hint

Try to use the brute-force approach iterating over different subarrays and checking whether they sum up to the required value ‘k’.

Approaches (2)
Brute Force

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. 

 

The steps are as follows:-
 

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

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

  1. Int ‘n’ be the size of the array ‘arr’.
  2. Initialize a variable ‘res’ initially assigned to ‘0’, which will store the number of subarrays with sum ‘k’.
  3. 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
  4. Return ‘res’.
Time Complexity

O( N^2 ), Where 'N' is the number of elements in the array/list 'arr'.

 

We are using a nested loop.
 

Hence, the time complexity is O( N^2 ).

Space Complexity

O( 1 ).
 

We are using some constants only.

 

Hence, the space complexity is O( 1 ).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Count All Subarrays With Given Sum
Full screen
Console