Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach 1 - Brute Force
3.1.
Code in C++
3.2.
Code in Python
3.3.
Code in Java
3.4.
Time Complexity
3.5.
Space Complexity
4.
Approach 2 - Prefix Sum
4.1.
Code in C++
4.2.
Code in Python 
4.3.
Code in Java
4.4.
Time Complexity
4.5.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is the time complexity of the decrease key method in Min Heap?
5.2.
What is the time complexity of insertion in priority_queue in C++ STL?
5.3.
What is the time complexity of deletion in priority_queue in C++ STL?
5.4.
What is the time complexity of finding the minimum in priority_queue in C++ STL?
5.5.
What is the time complexity of building a min-heap in a bottom-up manner?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Binary Subarrays with Sum

Author Husen Kagdi
3 upvotes
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

We study decimal numbers, which are base 10 numbers, in mathematics. On the other hand, the computer does not understand decimal numbers; it only understands two values: 'ON' or 'OFF,' or Binary Numbers.

Binary numbers are two base numbers with only two values: 0 and 1. Although the binary system is a simple notion representing two values, it has a wide range of problems. One of these problems will be discussed today.

How Binary Numbers Work - Alpenglow Industries

Let’s first start with understanding the problem in depth so that approaches can easily go through your mind.

Recommended topic, kth largest element in an array and  Euclid GCD Algorithm

Problem Statement

Given a binary array, that is, an array containing only ones and zeros and an integer goal, find the number of subarrays with the sum equal to the ‘GOAL.’ Recall that a subarray is a contiguous part of an array. Let's understand this with the help of an example for better clarity.

Example

ARRAY = [1, 0, 1, 1, 1, 0, 1], GOAL= 3.

The subarrays with the sum equal to the goal are:

[1, 0, 1, 1, 1, 0, 1]

[1, 0, 1, 1, 1, 0, 1]

[1, 0, 1, 1, 1, 0, 1]

[1, 0, 1, 1, 1, 0, 1]

[1, 0, 1, 1, 1, 0, 1]

[1, 0, 1, 1, 1, 0, 1]

Thus the output is 6.

Output: 6.

Before stepping towards the solution provided by us, try to ponder it by yourself; that will increase your thinking ability and mental skills. You can practice Subarray With the Given Sum problem on Coding Ninjas Studio to think of a more appropriate solution for this particular problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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()

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));
    }
}

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

Prefix sum

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;
}

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()

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));
    }
}

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 ArraysSubarray Sum 1Count Subarraysand 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!!

Previous article
Two Best Non-Overlapping Events
Next article
Hotel Bookings Possible
Live masterclass