Subarray Sums I
You are given an array of positive integers ‘ARR’ that represents the strengths of different “jutsus” (‘jutsu’ is a Japanese word for art i.e. ninja techniques) that a Ninja knows and can use to defeat enemies. You are also given the strength of the enemy ‘S’ (which is also a positive integer).

Your task is to count all the subarrays that have the combined strength as that of the given enemy and can help the Ninja to defeat the enemy.

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

Example:

Suppose given ‘ARR’ is [3, 1, 2, 4] and ‘S’ is 6 then The count of the subarrays in ‘ARR’ that sum up to 6 is 2, i.e. subarrays ‘ARR[0...2]’ and ‘ARR[2...3]’.

Input Format

The first line of input contains a single integer ‘T’ denoting the number of test cases given. Then next ‘T’ lines follow: The first line of each test case input contains two space-separated integers, where the first integer represents the length ‘ARR.length’ (‘N’) of the elements which would be given in the ‘ARR’ array/list while the second integer is the value ‘S’. 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 given strength ‘S’ of the enemy. Output for each test case should be in a separate line.

Note:

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

Constraint :

1

Question

Subarray Sums I

You are given an array of positive integers ‘ARR’ that represents the strengths of different “jutsus” (‘jutsu’ is a Japanese word for art i.e. ninja techniques) that a Ninja knows and can use to defeat enemies. You are also given the strength of the enemy ‘S’ (which is also a positive integer).

Your task is to count all the subarrays that have the combined strength as that of the given enemy and can help the Ninja to defeat the enemy.

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

Example:

Suppose given ‘ARR’ is [3, 1, 2, 4] and ‘S’ is 6 then
The count of the subarrays in ‘ARR’ that sum up to 6 is 2, i.e. subarrays ‘ARR[0...2]’ and ‘ARR[2...3]’.

Input Format

The first line of input contains a single integer ‘T’ denoting the number of test cases given. Then next ‘T’ lines follow:

The first line of each test case input contains two space-separated integers, where the first integer represents the length ‘ARR.length’ (‘N’) of the elements which would be given in the ‘ARR’ array/list while the second integer is the value ‘S’.

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 given strength ‘S’ of the enemy.

Output for each test case should be in a separate line.

Note:

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

Constraint :

1 <= ‘T’ <= 100
1 <= ‘N’<= 10^3
1 <= ‘ARR’[i] <= 10^9
1 <=  ‘S’ <= 10^9

Where ‘ARR[i]' is the 'i_th' element of array 'ARR'.

Time Limit: 1 sec

Accepted Answer

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 algorithm to calculate the required will be:-

Initialize a variable ‘RES’ as 0 to store the count of all the subarrays which sum up to the given value ‘S’.
Now, traverse the given array by iterating from 0 to ‘N’ which is the total size of the array and traverse again from the current index upto the end of the array (basically getting the subarrays).
Keep check If there exists a subarray from index upto ‘N’ having the sum equal to ‘S’ and keep incrementing the value of ‘RES’ if it does otherwise keep moving ahead and checking for all the other subarrays present in ‘ARR’.
Finally, return the result ‘RES’.

Space Complexity: O(1)Explanation:

O(1).

Since, Here, we are using constant space therefore space complexity is O(1).

Time Complexity: O(1)Explanation:

O(N^2), where ‘N’ is the number of elements in the array/list ‘ARR’.

Since we are iterating over all the elements of the array/list ‘ARR’, counting how many subarrays present in ‘ARR’ have sum equal to ‘S’ and increment the ‘RES’ accordingly hence, the complexity here grows by O(N^2).

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the array/list 'arr'.

*/



int findAllSubarraysWithGivenSum(vector < int > & arr, int s) {



    int n = arr.size();

    int res = 0;



    // Calculate all subarrays.

    for (int i = 0; i < n; i++) {

        int summ = 0;



        for (int j = i; j < n; j++) {



            // Calculate required sum.

            summ += arr[j];



            // Check if sum is equal to required sum.

            if (summ == s) {

                res += 1;

            }

        }

    }



    return res;

}

Java (SE 1.8)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the array/list 'arr'.

*/



public class Solution {

    public static int findAllSubarraysWithGivenSum(int arr[], int s) {

        int n = arr.length;

        int res = 0;

    

        // Calculate all subarrays.

        for (int i = 0; i < n; i++) {

            int summ = 0;

    

            for (int j = i; j < n; j++) {

    

                // Calculate required sum.

                summ += arr[j];

    

                // Check if sum is equal to required sum.

                if (summ == s) {

                    res += 1;

                }

            }

        }

    

        return res;

    } 

}

Python (3.5)

'''
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    Where ‘N’ is the number of elements in the array/list ‘ARR’.
'''

def findAllSubarraysWithGivenSum(arr, s):
    n = len(arr)
    res = 0
    
    # Calculate all subarrays.
    for i in range(n):
        summ = 0           
        for j in range(i, n):
            
            # Calculate required sum.
            summ += arr[j]
    
            # Check if sum is equal to required sum.
            if summ == s:
                res += 1
    
    return res

Accepted Answer

Hashing

An efficient solution is while traversing the array, we keep storing the sum that we have gotten so far in ‘CURRSUM’. Here would also need to maintain the count of different values of ‘CURRSUM’ in a map. 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’ - ‘TOTALSUM’), then if this value is removed from ‘CURRSUM’ then the desired sum can be obtained. From the map find the number of subarrays previously found having a sum equal to (‘CURRSUM’ - ‘TOTALSUM’). Excluding all those subarrays from the current subarray, gives new subarrays having the desired sum.