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.

The algorithm to calculate the required will be:-

Initialize a ‘CURRSUM’ variable with 0, ‘RES’ by 0, and a map to store all the count of subarrays having a sum equal to a particular ‘CURRSUM’ that we have created.
Now if we iterate through the ‘ARR’ array and keep finding out the value of ‘CURRSUM’ and check if it equals the value of ‘S’ then we increment the value of ‘RES’.
If the value of ‘CURRSUM’ exceeds the desired sum (which would be by a value (‘CURRSUM’ - ‘TOTALSUM’). So increase count by the number of such subarrays and remove this value from ‘CURRSUM’ which would then give us the desired sum can be obtained.
- In such a case, from the map that we have obtained, find the number of subarrays previously found having sum equal to (‘CURRSUM’ - ‘TOTALSUM’). Excluding all those subarrays from the current subarray, gives new subarrays having the desired sum.
Note that when ‘CURRSUM’ is equal to the desired sum then also we should check the number of subarrays previously having a sum equal to 0. Excluding those subarrays from the current subarray gives new subarrays having the desired sum. Here also we would increase the value of count by the number of subarrays having sum 0.
Finally, we can return the ‘RES’

Space Complexity: O(1)Explanation:

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

Here, we require an O(N) amount of space for storing the respective sums in the map for indexes, therefore, the space complexity is O(N).

Time Complexity: O(1)Explanation:

O(N), 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’ to calculate the prefix sums and checking their sums hence, the complexity here grows by O(N).

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



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

'''



from collections import defaultdict



def findAllSubarraysWithGivenSum(arr, s):

    # Used to store number of subarrays starting from index zero having particular value of sum.

    prevSum = defaultdict(lambda : 0)

    n = len(arr)

    res = 0

   

    # To keep track of sum of elements so far.

    currsum = 0

   

    for i in range(0, n): 

   

        # Add current element to sum so far.

        currsum += arr[i]

   

        # If current sum is equal to desired sum, then a new subarray is found. So, increase count of subarrays.

        if currsum == s: 

            res += 1        



        '''

            If current sum exceeds given sum by current sum  - sum. 

            Find number of subarrays having this sum in our map/dictionary and exclude these subarrays.

        '''

        if (currsum - s) in prevSum:

            res += prevSum[currsum - s]

           

   

        # Add current sum value to count of different values of sum.

        prevSum[currsum] += 1

      

    return res

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



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

*/



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



    // Used to store number of subarrays starting from index zero having particular value of sum.

    unordered_map < int, int > prevSum;

    int n = arr.size();

    int res = 0;



    // To keep track of sum of elements so far.

    int currsum = 0;



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



        // Add current element to sum so far.

        currsum += arr[i];



        // If current sum is equal to desired sum, then a new subarray is found. So, increase count of subarrays.

        if (currsum == s) {

            res += 1;

        }



        /*

            If current sum exceeds given sum by current sum  - sum then

            find the number of subarrays having this sum in our map and exclude these subarrays.

        */

        if (prevSum.find(currsum - s) != prevSum.end()) {



            res += prevSum[currsum - s];

        }



        // Add current sum value to count of different values of sum.

        prevSum[currsum] += 1;

    }



    return res;

}

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



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

*/



import java.util.HashMap;



public class Solution {

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

        // Used to store number of subarrays starting from index zero having particular value of sum.

        HashMap < Integer, Integer > prevSum = new HashMap();

        int n = arr.length;

        int res = 0;



        // To keep track of sum of elements so far.

        int currsum = 0;



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



            // Add current element to sum so far.

            currsum += arr[i];



            // If current sum is equal to desired sum, then a new subarray is found. So, increase count of subarrays.

            if (currsum == s) {

                res += 1;

            }

            

            /*

                If current sum exceeds given sum by current sum  - sum. 

                Find number of subarrays having this sum in our map and exclude these subarrays.

            */

            if (prevSum.containsKey(currsum - s)) {



                res += prevSum.get(currsum - s);

            }



            // Add current sum value to count of different values of sum.

            if(prevSum.containsKey(currsum)) {

                prevSum.put(currsum, prevSum.get(currsum) + 1);

            } else {

                prevSum.put(currsum, 1);

            }

        }



        return res;

    } 

}

Top SAP Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern