Count subarrays with equal number of 1’s and 0’s

Problem Statement

The problem “Count subarrays with equal number of 1’s and 0’s” states that you are given an array consisting of 0’s and 1’s only. The problem statement asks to find out the count of sub-arrays consisting equal no of 0’s ad 1’s.

Example

arr[] = {0, 0, 1, 1, 0}

4

Explanation: All the sub-arrays are (1,2), (3,4), (0,3), (1,4)

arr[] = {1,0,0,1,1,0}

7

Explanation: All the sub-arrays are (0, 1), (2,3), (0,3), (1,4), (0,5), (4,5), (2,5).

Algorithm

1. Declare the map.
2. Set the output and sum to 0.
3. Traverse the array, while i<n.
  1. Set arr[i] = -1, if arr[i] is equal to 0.
  2. Add the value of arr[i] to the sum.
  3. If the sum is equal to 0, then increase the value of output by 1.
  4. If the map contains the sum, then add the output to the frequency of the current sum’s value in the map.
  5. If the map contains the value sum, then just increase the frequency of the previous sum’s frequency in the map by 1.
  6. Else put that new sum and marks its frequency as 1.
4. Return output.

Explanation

We have given an array consisting of 0’s and 1’s only. So, we need to find out the count of the sub-arrays that contain 0’s and 1’s only. We are going to use Hashing. We will declare a map. In a map, we are going to store the sum and its frequency as 1. If it is new to the map then add it to the map, else increase the frequency of the previous sum’s value present in the map.

But before that, we will be converting all the 0’s to -1’s, while traversing the loop, If we found an array element as 0, we will be converting it to -1. Adding up the value of the current array element to the sum. We will check for the sum, if the sum is equal to 0, we are going to increase the value of output. This is because we are converting all the 0’s into -1’s and we have 1’s and 0’s only. So when we convert 0 into -1 and add that value with 1s. Whenever the sum is 0, this is only possible when we have equal 0’s and 1’s.

Suppose we have three 1’s and three 0’s, and converting each 0 into -1 and adding up the three 1 and three -1, we will have 0 as a sum. This also implies that after converting 0 into -1, to have 0 as sum, we should have equal 0 and 1. So, whenever you find the value of the sum as 0, we will increase the output value. Considering the input array, we will be updating the value of output whenever we get the sum as 0.

Code

C++ code to Count subarrays with equal number of 1’s and 0’s

#include <iostream>
#include<map>

using namespace std;

int getSubArrayWithEqual01(int arr[], int n)
{
    map<int,int> MAP;
    int sum=0;
    int output=0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
            arr[i] = -1;

        sum += arr[i];

        if (sum == 0)
            output++;

        if (MAP[sum])
            output += MAP[sum];

        if(MAP[sum]==0)
            MAP[sum]=1;
        else
            MAP[sum]++;
    }
    return output;
}
int main()
{
    int arr[] = { 0, 0, 1, 1, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Sub-Arrays with equal 0's and 1's count is: " <<getSubArrayWithEqual01(arr, n);
}

Sub-Arrays with equal 0's and 1's count is: 4

Java code to Count subarrays with equal number of 1’s and 0’s

import java.util.HashMap;
class SubArrayCount01
{
    public static int getSubArrayWithEqual01(int[] arr, int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<>();
        int sum = 0;
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == 0)
            {
                arr[i] = -1;
            }
            sum += arr[i];

            if (sum == 0)
            {
                output++;
            }
            if (MAP.containsKey(sum))
                output += MAP.get(sum);

            if (!MAP.containsKey(sum))
            {
                MAP.put(sum, 1);
            }
            else
            {
                MAP.put(sum, MAP.get(sum) + 1);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 0, 0, 1, 1, 0 };
        int n = arr.length;
        System.out.println("Sub-Arrays with equal 0's and 1's count is:" +getSubArrayWithEqual01(arr, n));
    }
}

Sub-Arrays with equal 0's and 1's count is:4

Complexity Analysis

Time C0mplexity

O(n) where “n” is the number of elements in the array. Because we have used HashMap we are able to achieve linear time complexity.

Space Complexity

O(n) where “n” is the number of elements in the array. Here in the HashMap we have saved the sum as key, thus linear space complexity is achieved.