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.

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

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.

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.

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

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

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.