Skip to main content

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

Here given code implementation process.

// 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




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