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 :", resultAlgorithm Explanation
- Initialize a 2D array
dpof size n x 2 to store the counts of subarrays for different net balances. - Iterate through the array
arrand initialize all entries ofdpto 0. - Traverse the array while updating the count based on ones and zeros and use the
dparray to count subarrays. - 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 : 2package 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 : 2import 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 : 2Time 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.
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