Posted on by Kalkicode
Code Dynamic Programming

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

The problem is a fascinating algorithmic challenge that involves finding the number of subarrays within a given binary array that have an equal count of ones and zeros. This problem has applications in data analysis, pattern recognition, and algorithm design. In this article, we'll delve into the approach to solving this problem using dynamic programming and provide detailed explanations along with code examples.

Problem Statement and Description

Given a binary array consisting of only ones and zeros, the goal is to determine the count of subarrays within the array where the number of ones is equal to the number of zeros. In other words, the task is to identify subarrays where the net balance between ones and zeros is zero.

Example

Consider the following examples to understand the concept:

  • For the binary array [0, 1, 0, 1]: The subarrays with equal counts of ones and zeros are [0, 1], [1, 0], [0, 1], and [1, 0]. The total count of such subarrays is 4.

  • For the binary array [1, 1, 1, 0, 1, 0, 1, 0]: The subarrays with equal counts of ones and zeros are [1, 0], [0, 1], [1, 0], [0, 1], [1, 0, 1, 0], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0], and [0, 1, 0, 1]. The total count of such subarrays is 9.

Idea to Solve the Problem

To solve the "Count subarrays with equal number of 1’s and 0’s" problem, we can use dynamic programming. The idea is to traverse the binary array while maintaining a count that keeps track of the difference between the number of ones and zeros seen so far. Whenever the count becomes the same as a previously encountered count, we can infer that the subarray between the two counts has an equal number of ones and zeros.

Standard Pseudocode

function countSame0s1s(arr, n):
    count = 0
    result = 0
    dp = 2D array of size n x 2
    
    for i from 0 to n:
        if arr[i] is not 0 and arr[i] is not 1:
            return  // Invalid input
    
    for i from 0 to n:
        dp[i][0] = 0
        dp[i][1] = 0
    
    dp[0][0] = 1
    
    for i from 0 to n:
        if arr[i] is 0:
            increment count
        else:
            decrement count
        
        if count < 0:
            increment result by dp[-count][1]
            increment dp[-count][1]
        else:
            increment result by dp[count][0]
            increment dp[count][0]
    
    print "Array :", arr
    print "Result :", result

Algorithm Explanation

  1. Initialize a 2D array dp of size n x 2 to store the counts of subarrays for different net balances.
  2. Iterate through the array arr and initialize all entries of dp to 0.
  3. Traverse the array while updating the count based on ones and zeros and use the dp array to count subarrays.
  4. Print the original array and the total count of subarrays with equal counts of ones and zeros.

Code Solution

// C Program
// Count subarrays with equal number of 1’s and 0’s
#include <stdio.h>

// Display array elements
void printArr(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
void countSame0s1s(int arr[], int n)
{
	int count = 0;
	int result = 0;
	// This is used to collect information of subarray
	// of zero and ones
	int dp[n][2];
	for (int i = 0; i < n; ++i)
	{
		if (arr[i] > 1 || arr[i] < 0)
		{
			// Array not contain 0 and 1
			return;
		}
		dp[i][0] = 0;
		dp[i][1] = 0;
	}
	dp[0][0] = 1;
	// Calculate subarray with equal number of 0s and 1s
	for (int i = 0; i < n; ++i)
	{
		if (arr[i] == 0)
		{
			count++;
		}
		else
		{
			count--;
		}
		if (count < 0)
		{
			result += dp[-count][1];
			dp[-count][1] += 1;
		}
		else
		{
			result += dp[count][0];
			dp[count][0] += 1;
		}
	}
	printArr(arr, n);
	printf(" Result : %d \n", result);
}
int main()
{
	// Sorted Arrays
	int a[] = {
		0 , 1 , 0 , 1
	};
	int b[] = {
		1 , 1 , 1 , 0 , 1 , 0 , 1 , 0
	};
	int c[] = {
		1 , 1 , 0 , 1
	};
	// Get the size
	int l1 = sizeof(a) / sizeof(a[0]);
	int l2 = sizeof(b) / sizeof(b[0]);
	int l3 = sizeof(c) / sizeof(c[0]);
	// Test A
	// arr = [0, 1, 0,1]
	// --------------------------
	//
	//  ➀  [0, 1, 0, 1]
	//  ➁        [0, 1]
	//  ➂  [0, 1]
	//  ➃     [1, 0]
	// ---------------
	//  Total : 4
	countSame0s1s(a, l1);
	// Test B
	// arr = [1, 1, 1, 0, 1, 0, 1, 0]
	// --------------------------
	//  ➀          [1, 0]
	//  ➁             [0, 1]
	//  ➂                [1, 0]
	//  ➃                   [0, 1]
	//  ➄                      [1, 0]
	//  ➅                [1, 0, 1, 0]
	//  ➆          [1, 0, 1, 0, 1, 0]
	//  ➇          [1, 0, 1, 0]
	//  ➈             [0, 1, 0, 1]
	// ---------------
	//  Total : 9
	countSame0s1s(b, l2);
	// Test C
	// arr = [1, 1, 0, 1]
	// --------------------------
	//  ➀       [1, 0]
	//  ➁          [0, 1]
	// ---------------
	//  Total : 2
	countSame0s1s(c, l3);
	return 0;
}

Output

  0  1  0  1
 Result : 4
  1  1  1  0  1  0  1  0
 Result : 9
  1  1  0  1
 Result : 2
/*
    Java Program
    Count subarrays with equal number of 1’s and 0’s
*/
public class Subarrays
{
	// Display array elements
	public void printArr(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i] );
		}
		System.out.print("\n");
	}
	public void countSame0s1s(int[] arr, int n)
	{
		int count = 0;
		int result = 0;
		// This is used to collect information of subarray
		// of zero and ones
		int[][] dp = new int[n][2];
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] > 1 || arr[i] < 0)
			{
				// Array not contain 0 and 1
				return;
			}
			dp[i][0] = 0;
			dp[i][1] = 0;
		}
		dp[0][0] = 1;
		// Calculate subarray with equal number of 0s and 1s
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] == 0)
			{
				count++;
			}
			else
			{
				count--;
			}
			if (count < 0)
			{
				result += dp[-count][1];
				dp[-count][1] += 1;
			}
			else
			{
				result += dp[count][0];
				dp[count][0] += 1;
			}
		}
		printArr(arr, n);
		System.out.print(" Result : " + result + " \n");
	}
	public static void main(String[] args)
	{
		Subarrays task = new Subarrays();
		// Sorted Arrays
		int[] a = {
			0 , 1 , 0 , 1
		};
		int[] b = {
			1 , 1 , 1 , 0 , 1 , 0 , 1 , 0
		};
		int[] c = {
			1 , 1 , 0 , 1
		};
		// Get the size
		int l1 = a.length;
		int l2 = b.length;
		int l3 = c.length;
		// Test A
		// arr = [0, 1, 0,1]
		// --------------------------
		//
		//  ➀  [0, 1, 0, 1]
		//  ➁        [0, 1]
		//  ➂  [0, 1]
		//  ➃     [1, 0]
		// ---------------
		//  Total : 4
		task.countSame0s1s(a, l1);
		// Test B
		// arr = [1, 1, 1, 0, 1, 0, 1, 0]
		// --------------------------
		//  ➀          [1, 0]
		//  ➁             [0, 1]
		//  ➂                [1, 0]
		//  ➃                   [0, 1]
		//  ➄                      [1, 0]
		//  ➅                [1, 0, 1, 0]
		//  ➆          [1, 0, 1, 0, 1, 0]
		//  ➇          [1, 0, 1, 0]
		//  ➈             [0, 1, 0, 1]
		// ---------------
		//  Total : 9
		task.countSame0s1s(b, l2);
		// Test C
		// arr = [1, 1, 0, 1]
		// --------------------------
		//  ➀       [1, 0]
		//  ➁          [0, 1]
		// ---------------
		//  Total : 2
		task.countSame0s1s(c, l3);
	}
}

Output

 0 1 0 1
 Result : 4
 1 1 1 0 1 0 1 0
 Result : 9
 1 1 0 1
 Result : 2
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program
    Count subarrays with equal number of 1’s and 0’s
*/
class Subarrays
{
	public:
		// Display array elements
		void printArr(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	void countSame0s1s(int arr[], int n)
	{
		int count = 0;
		int result = 0;
		// This is used to collect information of subarray
		// of zero and ones
		int dp[n][2];
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] > 1 || arr[i] < 0)
			{
				// Array not contain 0 and 1
				return;
			}
			dp[i][0] = 0;
			dp[i][1] = 0;
		}
		dp[0][0] = 1;
		// Calculate subarray with equal number of 0s and 1s
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] == 0)
			{
				count++;
			}
			else
			{
				count--;
			}
			if (count < 0)
			{
				result += dp[-count][1];
				dp[-count][1] += 1;
			}
			else
			{
				result += dp[count][0];
				dp[count][0] += 1;
			}
		}
		this->printArr(arr, n);
		cout << " Result : " << result << " \n";
	}
};
int main()
{
	Subarrays *task = new Subarrays();
	// Sorted Arrays
	int a[] = {
		0 , 1 , 0 , 1
	};
	int b[] = {
		1 , 1 , 1 , 0 , 1 , 0 , 1 , 0
	};
	int c[] = {
		1 , 1 , 0 , 1
	};
	// Get the size
	int l1 = sizeof(a) / sizeof(a[0]);
	int l2 = sizeof(b) / sizeof(b[0]);
	int l3 = sizeof(c) / sizeof(c[0]);
	// Test A
	// arr = [0, 1, 0,1]
	// --------------------------
	//
	//  ➀  [0, 1, 0, 1]
	//  ➁        [0, 1]
	//  ➂  [0, 1]
	//  ➃     [1, 0]
	// ---------------
	//  Total : 4
	task->countSame0s1s(a, l1);
	// Test B
	// arr = [1, 1, 1, 0, 1, 0, 1, 0]
	// --------------------------
	//  ➀          [1, 0]
	//  ➁             [0, 1]
	//  ➂                [1, 0]
	//  ➃                   [0, 1]
	//  ➄                      [1, 0]
	//  ➅                [1, 0, 1, 0]
	//  ➆          [1, 0, 1, 0, 1, 0]
	//  ➇          [1, 0, 1, 0]
	//  ➈             [0, 1, 0, 1]
	// ---------------
	//  Total : 9
	task->countSame0s1s(b, l2);
	// Test C
	// arr = [1, 1, 0, 1]
	// --------------------------
	//  ➀       [1, 0]
	//  ➁          [0, 1]
	// ---------------
	//  Total : 2
	task->countSame0s1s(c, l3);
	return 0;
}

Output

 0 1 0 1
 Result : 4
 1 1 1 0 1 0 1 0
 Result : 9
 1 1 0 1
 Result : 2
// Include namespace system
using System;
/*
    Csharp Program
    Count subarrays with equal number of 1’s and 0’s
*/
public class Subarrays
{
	// Display array elements
	public void printArr(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public void countSame0s1s(int[] arr, int n)
	{
		int count = 0;
		int result = 0;
		// This is used to collect information of subarray
		// of zero and ones
		int[,] dp = new int[n,2];
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] > 1 || arr[i] < 0)
			{
				// Array not contain 0 and 1
				return;
			}
			dp[i,0] = 0;
			dp[i,1] = 0;
		}
		dp[0,0] = 1;
		// Calculate subarray with equal number of 0s and 1s
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] == 0)
			{
				count++;
			}
			else
			{
				count--;
			}
			if (count < 0)
			{
				result += dp[-count,1];
				dp[-count,1] += 1;
			}
			else
			{
				result += dp[count,0];
				dp[count,0] += 1;
			}
		}
		this.printArr(arr, n);
		Console.Write(" Result : " + result + " \n");
	}
	public static void Main(String[] args)
	{
		Subarrays task = new Subarrays();
		// Sorted Arrays
		int[] a = {
			0 , 1 , 0 , 1
		};
		int[] b = {
			1 , 1 , 1 , 0 , 1 , 0 , 1 , 0
		};
		int[] c = {
			1 , 1 , 0 , 1
		};
		// Get the size
		int l1 = a.Length;
		int l2 = b.Length;
		int l3 = c.Length;
		// Test A
		// arr = [0, 1, 0,1]
		// --------------------------
		//
		//  ➀  [0, 1, 0, 1]
		//  ➁        [0, 1]
		//  ➂  [0, 1]
		//  ➃     [1, 0]
		// ---------------
		//  Total : 4
		task.countSame0s1s(a, l1);
		// Test B
		// arr = [1, 1, 1, 0, 1, 0, 1, 0]
		// --------------------------
		//  ➀          [1, 0]
		//  ➁             [0, 1]
		//  ➂                [1, 0]
		//  ➃                   [0, 1]
		//  ➄                      [1, 0]
		//  ➅                [1, 0, 1, 0]
		//  ➆          [1, 0, 1, 0, 1, 0]
		//  ➇          [1, 0, 1, 0]
		//  ➈             [0, 1, 0, 1]
		// ---------------
		//  Total : 9
		task.countSame0s1s(b, l2);
		// Test C
		// arr = [1, 1, 0, 1]
		// --------------------------
		//  ➀       [1, 0]
		//  ➁          [0, 1]
		// ---------------
		//  Total : 2
		task.countSame0s1s(c, l3);
	}
}

Output

 0 1 0 1
 Result : 4
 1 1 1 0 1 0 1 0
 Result : 9
 1 1 0 1
 Result : 2
package main
import "fmt"
/*
    Go Program
    Count subarrays with equal number of 1’s and 0’s
*/

// Display array elements
func printArr(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
	fmt.Print("\n")
}
func countSame0s1s(arr[] int, n int) {
	var count int = 0
	var result int = 0
	// This is used to collect information of subarray
	// of zero and ones
	var dp = make([][] int, n)
	for i := 0; i < n; i++{
		dp[i] = make([]int,2)
	}
	for i := 0 ; i < n ; i++ {
		if arr[i] > 1 || arr[i] < 0 {
			// Array not contain 0 and 1
			return
		}
		dp[i][0] = 0
		dp[i][1] = 0
	}
	dp[0][0] = 1
	// Calculate subarray with equal number of 0s and 1s
	for i := 0 ; i < n ; i++ {
		if arr[i] == 0 {
			count++
		} else {
			count--
		}
		if count < 0 {
			result += dp[-count][1]
			dp[-count][1] += 1
		} else {
			result += dp[count][0]
			dp[count][0] += 1
		}
	}
	printArr(arr, n)
	fmt.Print(" Result : ", result, " \n")
}
func main() {

	// Sorted Arrays
	var a = [] int {
		0,
		1,
		0,
		1,
	}
	var b = [] int {
		1,
		1,
		1,
		0,
		1,
		0,
		1,
		0,
	}
	var c = [] int {
		1,
		1,
		0,
		1,
	}
	// Get the size
	var l1 int = len(a)
	var l2 int = len(b)
	var l3 int = len(c)
	// Test A
	// arr = [0, 1, 0,1]
	// --------------------------
	//
	//  ➀  [0, 1, 0, 1]
	//  ➁        [0, 1]
	//  ➂  [0, 1]
	//  ➃     [1, 0]
	// ---------------
	//  Total : 4
	countSame0s1s(a, l1)
	// Test B
	// arr = [1, 1, 1, 0, 1, 0, 1, 0]
	// --------------------------
	//  ➀          [1, 0]
	//  ➁             [0, 1]
	//  ➂                [1, 0]
	//  ➃                   [0, 1]
	//  ➄                      [1, 0]
	//  ➅                [1, 0, 1, 0]
	//  ➆          [1, 0, 1, 0, 1, 0]
	//  ➇          [1, 0, 1, 0]
	//  ➈             [0, 1, 0, 1]
	// ---------------
	//  Total : 9
	countSame0s1s(b, l2)
	// Test C
	// arr = [1, 1, 0, 1]
	// --------------------------
	//  ➀       [1, 0]
	//  ➁          [0, 1]
	// ---------------
	//  Total : 2
	countSame0s1s(c, l3)
}

Output

 0 1 0 1
 Result : 4
 1 1 1 0 1 0 1 0
 Result : 9
 1 1 0 1
 Result : 2
<?php
/*
    Php Program
    Count subarrays with equal number of 1’s and 0’s
*/
class Subarrays
{
	// Display array elements
	public	function printArr($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
		echo("\n");
	}
	public	function countSame0s1s($arr, $n)
	{
		$count = 0;
		$result = 0;
		// This is used to collect information of subarray
		// of zero and ones
		$dp = array_fill(0, $n, array_fill(0, 2, 0));
		for ($i = 0; $i < $n; ++$i)
		{
			if ($arr[$i] > 1 || $arr[$i] < 0)
			{
				// Array not contain 0 and 1
				return;
			}
			$dp[$i][0] = 0;
			$dp[$i][1] = 0;
		}
		$dp[0][0] = 1;
		// Calculate subarray with equal number of 0s and 1s
		for ($i = 0; $i < $n; ++$i)
		{
			if ($arr[$i] == 0)
			{
				$count++;
			}
			else
			{
				$count--;
			}
			if ($count < 0)
			{
				$result += $dp[-$count][1];
				$dp[-$count][1] += 1;
			}
			else
			{
				$result += $dp[$count][0];
				$dp[$count][0] += 1;
			}
		}
		$this->printArr($arr, $n);
		echo(" Result : ".$result." \n");
	}
}

function main()
{
	$task = new Subarrays();
	// Sorted Arrays
	$a = array(0, 1, 0, 1);
	$b = array(1, 1, 1, 0, 1, 0, 1, 0);
	$c = array(1, 1, 0, 1);
	// Get the size
	$l1 = count($a);
	$l2 = count($b);
	$l3 = count($c);
	// Test A
	// arr = [0, 1, 0,1]
	// --------------------------
	//
	//  ➀  [0, 1, 0, 1]
	//  ➁        [0, 1]
	//  ➂  [0, 1]
	//  ➃     [1, 0]
	// ---------------
	//  Total : 4
	$task->countSame0s1s($a, $l1);
	// Test B
	// arr = [1, 1, 1, 0, 1, 0, 1, 0]
	// --------------------------
	//  ➀          [1, 0]
	//  ➁             [0, 1]
	//  ➂                [1, 0]
	//  ➃                   [0, 1]
	//  ➄                      [1, 0]
	//  ➅                [1, 0, 1, 0]
	//  ➆          [1, 0, 1, 0, 1, 0]
	//  ➇          [1, 0, 1, 0]
	//  ➈             [0, 1, 0, 1]
	// ---------------
	//  Total : 9
	$task->countSame0s1s($b, $l2);
	// Test C
	// arr = [1, 1, 0, 1]
	// --------------------------
	//  ➀       [1, 0]
	//  ➁          [0, 1]
	// ---------------
	//  Total : 2
	$task->countSame0s1s($c, $l3);
}
main();

Output

 0 1 0 1
 Result : 4
 1 1 1 0 1 0 1 0
 Result : 9
 1 1 0 1
 Result : 2
/*
    Node JS Program
    Count subarrays with equal number of 1’s and 0’s
*/
class Subarrays
{
	// Display array elements
	printArr(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	countSame0s1s(arr, n)
	{
		var count = 0;
		var result = 0;
		// This is used to collect information of subarray
		// of zero and ones
		var dp = Array(n).fill(0).map(() => new Array(2).fill(0));
		for (var i = 0; i < n; ++i)
		{
			if (arr[i] > 1 || arr[i] < 0)
			{
				// Array not contain 0 and 1
				return;
			}
			dp[i][0] = 0;
			dp[i][1] = 0;
		}
		dp[0][0] = 1;
		// Calculate subarray with equal number of 0s and 1s
		for (var i = 0; i < n; ++i)
		{
			if (arr[i] == 0)
			{
				count++;
			}
			else
			{
				count--;
			}
			if (count < 0)
			{
				result += dp[-count][1];
				dp[-count][1] += 1;
			}
			else
			{
				result += dp[count][0];
				dp[count][0] += 1;
			}
		}
		this.printArr(arr, n);
		process.stdout.write(" Result : " + result + " \n");
	}
}

function main()
{
	var task = new Subarrays();
	// Sorted Arrays
	var a = [0, 1, 0, 1];
	var b = [1, 1, 1, 0, 1, 0, 1, 0];
	var c = [1, 1, 0, 1];
	// Get the size
	var l1 = a.length;
	var l2 = b.length;
	var l3 = c.length;
	// Test A
	// arr = [0, 1, 0,1]
	// --------------------------
	//
	//  ➀  [0, 1, 0, 1]
	//  ➁        [0, 1]
	//  ➂  [0, 1]
	//  ➃     [1, 0]
	// ---------------
	//  Total : 4
	task.countSame0s1s(a, l1);
	// Test B
	// arr = [1, 1, 1, 0, 1, 0, 1, 0]
	// --------------------------
	//  ➀          [1, 0]
	//  ➁             [0, 1]
	//  ➂                [1, 0]
	//  ➃                   [0, 1]
	//  ➄                      [1, 0]
	//  ➅                [1, 0, 1, 0]
	//  ➆          [1, 0, 1, 0, 1, 0]
	//  ➇          [1, 0, 1, 0]
	//  ➈             [0, 1, 0, 1]
	// ---------------
	//  Total : 9
	task.countSame0s1s(b, l2);
	// Test C
	// arr = [1, 1, 0, 1]
	// --------------------------
	//  ➀       [1, 0]
	//  ➁          [0, 1]
	// ---------------
	//  Total : 2
	task.countSame0s1s(c, l3);
}
main();

Output

 0 1 0 1
 Result : 4
 1 1 1 0 1 0 1 0
 Result : 9
 1 1 0 1
 Result : 2
#    Python 3 Program
#    Count subarrays with equal number of 1’s and 0’s
class Subarrays :
	#  Display list elements
	def printArr(self, arr, n) :
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	def countSame0s1s(self, arr, n) :
		count = 0
		result = 0
		#  This is used to collect information of sublist
		#  of zero and ones
		dp = [[0] * (2) for _ in range(n) ]
		i = 0
		while (i < n) :
			if (arr[i] > 1 or arr[i] < 0) :
				#  Array not contain 0 and 1
				return
			
			dp[i][0] = 0
			dp[i][1] = 0
			i += 1
		
		dp[0][0] = 1
		i = 0
		#  Calculate sublist with equal number of 0s and 1s
		while (i < n) :
			if (arr[i] == 0) :
				count += 1
			else :
				count -= 1
			
			if (count < 0) :
				result += dp[-count][1]
				dp[-count][1] += 1
			else :
				result += dp[count][0]
				dp[count][0] += 1
			
			i += 1
		
		self.printArr(arr, n)
		print(" Result : ", result ," ")
	

def main() :
	task = Subarrays()
	#  Sorted Arrays
	a = [0, 1, 0, 1]
	b = [1, 1, 1, 0, 1, 0, 1, 0]
	c = [1, 1, 0, 1]
	#  Get the size
	l1 = len(a)
	l2 = len(b)
	l3 = len(c)
	#  Test A
	#  arr = [0, 1, 0,1]
	#  --------------------------
	#   ➀  [0, 1, 0, 1]
	#   ➁        [0, 1]
	#   ➂  [0, 1]
	#   ➃     [1, 0]
	#  ---------------
	#   Total : 4
	task.countSame0s1s(a, l1)
	#  Test B
	#  arr = [1, 1, 1, 0, 1, 0, 1, 0]
	#  --------------------------
	#   ➀          [1, 0]
	#   ➁             [0, 1]
	#   ➂                [1, 0]
	#   ➃                   [0, 1]
	#   ➄                      [1, 0]
	#   ➅                [1, 0, 1, 0]
	#   ➆          [1, 0, 1, 0, 1, 0]
	#   ➇          [1, 0, 1, 0]
	#   ➈             [0, 1, 0, 1]
	#  -------------------------------
	#   Total : 9
	task.countSame0s1s(b, l2)
	#  Test C
	#  arr = [1, 1, 0, 1]
	#  --------------------------
	#   ➀       [1, 0]
	#   ➁          [0, 1]
	#  ---------------
	#   Total : 2
	task.countSame0s1s(c, l3)

if __name__ == "__main__": main()

Output

  0  1  0  1
 Result :  4
  1  1  1  0  1  0  1  0
 Result :  9
  1  1  0  1
 Result :  2
#    Ruby Program
#    Count subarrays with equal number of 1’s and 0’s
class Subarrays 
	#  Display array elements
	def printArr(arr, n) 
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

		print("\n")
	end

	def countSame0s1s(arr, n) 
		count = 0
		result = 0
		#  This is used to collect information of subarray
		#  of zero and ones
		dp = Array.new(n) {Array.new(2) {0}}
		i = 0
		while (i < n) 
			if (arr[i] > 1 || arr[i] < 0) 
				#  Array not contain 0 and 1
				return
			end

			dp[i][0] = 0
			dp[i][1] = 0
			i += 1
		end

		dp[0][0] = 1
		i = 0
		#  Calculate subarray with equal number of 0s and 1s
		while (i < n) 
			if (arr[i] == 0) 
				count += 1
			else
 
				count -= 1
			end

			if (count < 0) 
				result += dp[-count][1]
				dp[-count][1] += 1
			else
 
				result += dp[count][0]
				dp[count][0] += 1
			end

			i += 1
		end

		self.printArr(arr, n)
		print(" Result : ", result ," \n")
	end

end

def main() 
	task = Subarrays.new()
	#  Sorted Arrays
	a = [0, 1, 0, 1]
	b = [1, 1, 1, 0, 1, 0, 1, 0]
	c = [1, 1, 0, 1]
	#  Get the size
	l1 = a.length
	l2 = b.length
	l3 = c.length
	#  Test A
	#  arr = [0, 1, 0,1]
	#  --------------------------
	#   ➀  [0, 1, 0, 1]
	#   ➁        [0, 1]
	#   ➂  [0, 1]
	#   ➃     [1, 0]
	#  ---------------
	#   Total : 4
	task.countSame0s1s(a, l1)
	#  Test B
	#  arr = [1, 1, 1, 0, 1, 0, 1, 0]
	#  --------------------------
	#   ➀          [1, 0]
	#   ➁             [0, 1]
	#   ➂                [1, 0]
	#   ➃                   [0, 1]
	#   ➄                      [1, 0]
	#   ➅                [1, 0, 1, 0]
	#   ➆          [1, 0, 1, 0, 1, 0]
	#   ➇          [1, 0, 1, 0]
	#   ➈             [0, 1, 0, 1]
	#  ------------------------------
	#   Total : 9
	task.countSame0s1s(b, l2)
	#  Test C
	#  arr = [1, 1, 0, 1]
	#  --------------------------
	#   ➀       [1, 0]
	#   ➁          [0, 1]
	#  ---------------
	#   Total : 2
	task.countSame0s1s(c, l3)
end

main()

Output

 0 1 0 1
 Result : 4 
 1 1 1 0 1 0 1 0
 Result : 9 
 1 1 0 1
 Result : 2 
/*
    Scala Program
    Count subarrays with equal number of 1’s and 0’s
*/
class Subarrays()
{
	// Display array elements
	def printArr(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	def countSame0s1s(arr: Array[Int], n: Int): Unit = {
		var count: Int = 0;
		var result: Int = 0;
		// This is used to collect information of subarray
		// of zero and ones
		var dp: Array[Array[Int]] = Array.fill[Int](n, 2)(0);
		var i: Int = 0;
		while (i < n)
		{
			if (arr(i) > 1 || arr(i) < 0)
			{
				// Array not contain 0 and 1
				return;
			}
			dp(i)(0) = 0;
			dp(i)(1) = 0;
			i += 1;
		}
		dp(0)(0) = 1;
		i = 0;
		// Calculate subarray with equal number of 0s and 1s
		while (i < n)
		{
			if (arr(i) == 0)
			{
				count += 1;
			}
			else
			{
				count -= 1;
			}
			if (count < 0)
			{
				result += dp(-count)(1);
				dp(-count)(1) += 1;
			}
			else
			{
				result += dp(count)(0);
				dp(count)(0) += 1;
			}
			i += 1;
		}
		printArr(arr, n);
		print(" Result : " + result + " \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subarrays = new Subarrays();
		// Sorted Arrays
		var a: Array[Int] = Array(0, 1, 0, 1);
		var b: Array[Int] = Array(1, 1, 1, 0, 1, 0, 1, 0);
		var c: Array[Int] = Array(1, 1, 0, 1);
		// Get the size
		var l1: Int = a.length;
		var l2: Int = b.length;
		var l3: Int = c.length;
		// Test A
		// arr = [0, 1, 0,1]
		// --------------------------
		//
		//  ➀  [0, 1, 0, 1]
		//  ➁        [0, 1]
		//  ➂  [0, 1]
		//  ➃     [1, 0]
		// ---------------
		//  Total : 4
		task.countSame0s1s(a, l1);
		// Test B
		// arr = [1, 1, 1, 0, 1, 0, 1, 0]
		// --------------------------
		//  ➀          [1, 0]
		//  ➁             [0, 1]
		//  ➂                [1, 0]
		//  ➃                   [0, 1]
		//  ➄                      [1, 0]
		//  ➅                [1, 0, 1, 0]
		//  ➆          [1, 0, 1, 0, 1, 0]
		//  ➇          [1, 0, 1, 0]
		//  ➈             [0, 1, 0, 1]
		// ---------------
		//  Total : 9
		task.countSame0s1s(b, l2);
		// Test C
		// arr = [1, 1, 0, 1]
		// --------------------------
		//  ➀       [1, 0]
		//  ➁          [0, 1]
		// ---------------
		//  Total : 2
		task.countSame0s1s(c, l3);
	}
}

Output

 0 1 0 1
 Result : 4
 1 1 1 0 1 0 1 0
 Result : 9
 1 1 0 1
 Result : 2
import Foundation;
/*
    Swift 4 Program
    Count subarrays with equal number of 1’s and 0’s
*/
class Subarrays
{
	// Display array elements
	func printArr(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	func countSame0s1s(_ arr: [Int], _ n: Int)
	{
		var count: Int = 0;
		var result: Int = 0;
		// This is used to collect information of subarray
		// of zero and ones
		var dp: [
			[Int]
		] = Array(repeating: Array(repeating: 0, count: 2), count: n);
		var i: Int = 0;
		while (i < n)
		{
			if (arr[i] > 1 || arr[i] < 0)
			{
				// Array not contain 0 and 1
				return;
			}
			dp[i][0] = 0;
			dp[i][1] = 0;
			i += 1;
		}
		dp[0][0] = 1;
		i = 0;
		// Calculate subarray with equal number of 0s and 1s
		while (i < n)
		{
			if (arr[i] == 0)
			{
				count += 1;
			}
			else
			{
				count -= 1;
			}
			if (count < 0)
			{
				result += dp[-count][1];
				dp[-count][1] += 1;
			}
			else
			{
				result += dp[count][0];
				dp[count][0] += 1;
			}
			i += 1;
		}
		self.printArr(arr, n);
		print(" Result : ", result ," ");
	}
}
func main()
{
	let task: Subarrays = Subarrays();
	// Sorted Arrays
	let a: [Int] = [0, 1, 0, 1];
	let b: [Int] = [1, 1, 1, 0, 1, 0, 1, 0];
	let c: [Int] = [1, 1, 0, 1];
	// Get the size
	let l1: Int = a.count;
	let l2: Int = b.count;
	let l3: Int = c.count;
	// Test A
	// arr = [0, 1, 0,1]
	// --------------------------
	//
	//  ➀  [0, 1, 0, 1]
	//  ➁        [0, 1]
	//  ➂  [0, 1]
	//  ➃     [1, 0]
	// ---------------
	//  Total : 4
	task.countSame0s1s(a, l1);
	// Test B
	// arr = [1, 1, 1, 0, 1, 0, 1, 0]
	// --------------------------
	//  ➀          [1, 0]
	//  ➁             [0, 1]
	//  ➂                [1, 0]
	//  ➃                   [0, 1]
	//  ➄                      [1, 0]
	//  ➅                [1, 0, 1, 0]
	//  ➆          [1, 0, 1, 0, 1, 0]
	//  ➇          [1, 0, 1, 0]
	//  ➈             [0, 1, 0, 1]
	// ---------------
	//  Total : 9
	task.countSame0s1s(b, l2);
	// Test C
	// arr = [1, 1, 0, 1]
	// --------------------------
	//  ➀       [1, 0]
	//  ➁          [0, 1]
	// ---------------
	//  Total : 2
	task.countSame0s1s(c, l3);
}
main();

Output

  0  1  0  1
 Result :  4
  1  1  1  0  1  0  1  0
 Result :  9
  1  1  0  1
 Result :  2
/*
    Kotlin Program
    Count subarrays with equal number of 1’s and 0’s
*/
class Subarrays
{
	// Display array elements
	fun printArr(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
		print("\n");
	}
	fun countSame0s1s(arr: Array < Int > , n: Int): Unit
	{
		var count: Int = 0;
		var result: Int = 0;
		// This is used to collect information of subarray
		// of zero and ones
		val dp: Array < Array < Int >> = Array(n)
		{
			Array(2)
			{
				0
			}
		};
		var i: Int = 0;
		while (i < n)
		{
			if (arr[i] > 1 || arr[i] < 0)
			{
				// Array not contain 0 and 1
				return;
			}
			dp[i][0] = 0;
			dp[i][1] = 0;
			i += 1;
		}
		dp[0][0] = 1;
		i = 0;
		// Calculate subarray with equal number of 0s and 1s
		while (i < n)
		{
			if (arr[i] == 0)
			{
				count += 1;
			}
			else
			{
				count -= 1;
			}
			if (count < 0)
			{
				result += dp[-count][1];
				dp[-count][1] += 1;
			}
			else
			{
				result += dp[count][0];
				dp[count][0] += 1;
			}
			i += 1;
		}
		this.printArr(arr, n);
		print(" Result : " + result + " \n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subarrays = Subarrays();
	// Sorted Arrays
	val a: Array < Int > = arrayOf(0, 1, 0, 1);
	val b: Array < Int > = arrayOf(1, 1, 1, 0, 1, 0, 1, 0);
	val c: Array < Int > = arrayOf(1, 1, 0, 1);
	// Get the size
	val l1: Int = a.count();
	val l2: Int = b.count();
	val l3: Int = c.count();
	// Test A
	// arr = [0, 1, 0,1]
	// --------------------------
	//
	//  ➀  [0, 1, 0, 1]
	//  ➁        [0, 1]
	//  ➂  [0, 1]
	//  ➃     [1, 0]
	// ---------------
	//  Total : 4
	task.countSame0s1s(a, l1);
	// Test B
	// arr = [1, 1, 1, 0, 1, 0, 1, 0]
	// --------------------------
	//  ➀          [1, 0]
	//  ➁             [0, 1]
	//  ➂                [1, 0]
	//  ➃                   [0, 1]
	//  ➄                      [1, 0]
	//  ➅                [1, 0, 1, 0]
	//  ➆          [1, 0, 1, 0, 1, 0]
	//  ➇          [1, 0, 1, 0]
	//  ➈             [0, 1, 0, 1]
	// ---------------
	//  Total : 9
	task.countSame0s1s(b, l2);
	// Test C
	// arr = [1, 1, 0, 1]
	// --------------------------
	//  ➀       [1, 0]
	//  ➁          [0, 1]
	// ---------------
	//  Total : 2
	task.countSame0s1s(c, l3);
}

Output

 0 1 0 1
 Result : 4
 1 1 1 0 1 0 1 0
 Result : 9
 1 1 0 1
 Result : 2

Time Complexity

The time complexity of the provided algorithm is O(n), where n is the length of the input array. This is because the algorithm iterates through the array only once. The space complexity is O(n) as well due to the storage of the dynamic programming array.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment