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 : 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 : 2
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