Binary Subarrays with Sum

Approach 1 - Brute Force

This is a brute-force approach. In this approach, we find every subarray and calculate its sum. If the sum is equal to the goal, we increment the answer.

We can find all the subarrays using two nested loops. Have a look at the code given below.

Note: Read out to Type of Algorithms for future reference.

Code in C++

#include <iostream>
#include <vector>
using namespace std;

// Function that calculates the number of subarrays in a binary array with sum 'GOAL'.
int countBinaryArraySum(vector<int> &a, int goal){
    int n = a.size();
    int count = 0;

    for(int i=0; i<n; i++){
        int subarraySum = 0;
        for(int j=i; j<n; j++){
            subarraySum += a[j];
            if(goal == subarraySum){
                count++;
            }
        }
    }
    return count;
}

int main(){
   vector<int> v = {1, 0, 1, 1, 1, 0, 1};
   int goal = 3;
   int ans = countBinaryArraySum(v, goal);
   cout << "Number of binary subarrays with sum 'GOAL': " << ans << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Code in Python

def countBinaryArraySum(a, goal):
    n = len(a)
    count = 0

    for i in range(len(a)):
        subArraySum = 0
        for j in range(i, len(a)):
            subArraySum += a[j]
            if subArraySum == goal:
                count += 1
       
    return count

def main():
    a = [1, 0, 1, 1, 1, 0, 1]
    goal = 3

    print("Number of binary subarrays with sum 'GOAL': ", countBinaryArraySum(a, goal))
main()

You can also try this code with Online Python Compiler

Run Code

Code in Java

// Java program for checking
// balanced brackets
import java.util.*;

public class Main {

    static int countBinaryArraySum(int []a, int goal){
        int n = a.length;
        int count = 0;

        for(int i=0; i<n; i++){
            int subarraySum = 0;
            for(int j=i; j<n; j++){
                subarraySum += a[j];
                if(goal == subarraySum){
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args){
        int a[] = {1, 0, 1, 1, 1, 0, 1};
        int goal = 3;

        System.out.println("Number of binary subarrays with sum 'GOAL': "+ countBinaryArraySum(a, goal));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Number of binary subarrays with sum 'GOAL': 6

Time Complexity

O(N ^ 2), where ‘N’ is the size of the array.

We find all the subarrays of the array with two nested loops. Hence the time complexity is  O(N ^ 2). 

Space Complexity

O(1).

We are only declaring a few variables. Thus it takes constant space.

You can also read about the Longest Consecutive Sequence.

Approach 2 - Prefix Sum

In this approach, we’ll find the prefix sum of the array, and for each index, in the array, we’ll check the count of the previous subarray whose prefix sum plus the ‘GOAL’ is equal to the current prefix sum and add it to the final ‘COUNT.’

What is the prefix sum?

A simple yet powerful technique allows for the fast calculation of sums of elements in a given slice (contiguous segments of an array). Its main idea uses prefix sums which are defined as the consecutive totals of the first 0, 1, 2, . . . , n elements of an array.

Example

So for each ‘END’, we will find the count of subarrays whose prefix sum plus goal equals the current prefix sum.

Let’s see how the algorithm works.

• Initialize a ‘PREFIX_SUM’ array and calculate the prefix sum for each index in array ‘NUMS.’
• Next, create a hashmap ‘MP’ to store the count of subarrays with the sum ‘PREFIX_SUM[START] + GOAL.’
• Now loop through the array ‘PREFIX_SUM’ and add the count of the previous subarrays to the answer.

Code in C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
 
int countBinaryArraySum(vector<int>arr, int goal){
    int n = arr.size();
    unordered_map<int, int> prevSum;
    int cnt = 0;
    int currsum = 0;
    for (int i = 0; i < n; i++) {
        currsum += arr[i];
        if (currsum == goal)
            cnt++;
        if (prevSum.find(currsum - goal) != prevSum.end())
            cnt += (prevSum[currsum - goal]);
        prevSum[currsum]++;
    }
    return cnt;
}

int main(){
   vector<int> v = {1, 0, 1, 1, 1, 0, 1};
   int goal = 3;
   int ans = countBinaryArraySum(v, goal);
   cout << "Number of binary subarrays with sum 'GOAL': " << ans << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Code in Python 

from collections import defaultdict

def countBinaryArraySum(a, goal):
    count, currsum = 0, 0
    prevsum = defaultdict(int)
    for i in a:
        currsum += i
        if currsum == goal:
            count += 1
        if (currsum-goal) in prevsum:
            count += prevsum[currsum-goal]
        prevsum[currsum] += 1
       
    return count

def main():
    a = [1, 0, 1, 1, 1, 0, 1]
    goal = 3
    print("Number of binary subarrays with sum 'GOAL': ", countBinaryArraySum(a, goal))

main()

You can also try this code with Online Python Compiler

Run Code

Code in Java

// Java program for checking
// balanced brackets
import java.util.*;
import java.util.HashMap;
import java.util.Map;

public class Main {

    static int countBinaryArraySum(int []a, int goal){
        int n = a.length;
        int cnt = 0;

        HashMap<Integer, Integer> prevSum = new HashMap<>();
        prevSum.put(0,1);

        int currsum = 0;
        for (int i = 0; i < n; i++) {
            currsum += a[i];

            if (currsum == goal)
                cnt++;

            if (prevSum.containsKey(currsum - goal))
                cnt += prevSum.get(currsum-goal);
   
            prevSum.put(currsum, prevSum.getOrDefault(currsum,0)+1);
        }
        return cnt;
    }

    public static void main(String[] args){
        int a[] = {1, 0, 1, 1, 1, 0, 1};
        int goal = 3;

        System.out.println("Number of binary subarrays with sum 'GOAL': "+ countBinaryArraySum(a, goal));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Number of binary subarrays with sum 'GOAL': 6

Time Complexity

O(N), where ‘N’ is the size of the array.

We are traversing the ‘NUMS’ and  ‘PREFIX_SUM’ array of size ‘N’ once. Hence the time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the size of the array.

As we are initializing array ‘PREFIX_SUM’ of size N.

Must read decimal to binary c++ 

Frequently Asked Questions

What is the time complexity of the decrease key method in Min Heap?

The time complexity of the decrease key method is O(Logn).

What is the time complexity of insertion in priority_queue in C++ STL?

The time complexity of insertion is O(Logn), where n is the number of elements in the priority_queue.

What is the time complexity of deletion in priority_queue in C++ STL?

The time complexity of deletion is O(Logn), where n is the number of elements in the priority_queue.

What is the time complexity of finding the minimum in priority_queue in C++ STL?

The time complexity of finding the minimum is O(1), which is a constant time complexity.

What is the time complexity of building a min-heap in a bottom-up manner?

The time complexity of building a min-heap in a bottom-up manner is O(n), where n is the number of elements.

Conclusion

Cheers if you reached here!! 

In this article, we can conclude that we have completed a problem using unordered_map in C++.

I would like you to suggest some problems for practice, same as that of this problem→ Sum Of Two Arrays, Subarray Sum 1, Count Subarrays, and K Sum Subset.

Also, you can refer to this suggested article which will give you insights into questions about different Data Structures.

Try some Practice Problems as well.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, DBMS, Basics of C++, etc. as well as some Test Series, Interview Bundles, and Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!!