Largest subarray with equal number of 0s and 1s
Here given code implementation process.
/*
Java program
Largest subarray with equal number of 0s and 1s
*/
import java.util.HashMap;
public class SubArraySum
{
// This function are displaying given array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
// Find the subarray of equal number of 0s and 1s
public void zeroSumSubarray(int[] arr, int n)
{
// Display given array elements
System.out.print("\n Array :");
display(arr, n);
int front = -1;
int tail = -1;
HashMap < Integer, Integer > result = new HashMap < Integer, Integer > ();
int sum = 0;
int i = 0;
// Execute loop through by size of array elements
for (i = 0; i < n; ++i)
{
if (arr[i] == 1)
{
sum += 1;
}
else if (arr[i] == 0)
{
sum -= 1;
}
else
{
// When array contains another number
return;
}
if (sum == 0)
{
front = i + 1;
tail = i;
}
if (result.containsKey(sum + n))
{
if (front < i - result.get(sum + n))
{
front = i - result.get(sum + n);
tail = i;
}
}
else
{
// Add the current sum
result.put(sum + n, i);
}
}
if (tail == -1)
{
System.out.print("None");
}
else
{
System.out.print(" Front " + (tail - front + 1) + " Tail " + tail);
}
}
public static void main(String[] args)
{
SubArraySum task = new SubArraySum();
// Case 1
// Define the array of (0,1) elements
int[] arr1 = {
1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0
};
int n = arr1.length;
task.zeroSumSubarray(arr1, n);
// Case 2
// Define the array of (0,1) elements
int[] arr2 = {
1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 1
};
n = arr2.length;
task.zeroSumSubarray(arr2, n);
}
}
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
// Include header file
#include <iostream>
#include <unordered_map>
using namespace std;
class SubArraySum
{
public:
// This function are displaying given array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
// Find the subarray of equal number of 0s and 1s
void zeroSumSubarray(int arr[], int n)
{
// Display given array elements
cout << "\n Array :";
this->display(arr, n);
int front = -1;
int tail = -1;
unordered_map < int, int > result ;
int sum = 0;
int i = 0;
// Execute loop through by size of array elements
for (i = 0; i < n; ++i)
{
if (arr[i] == 1)
{
sum += 1;
}
else if (arr[i] == 0)
{
sum -= 1;
}
else
{
// When array contains another number
return;
}
if (sum == 0)
{
front = i + 1;
tail = i;
}
if (result.find(sum + n) != result.end())
{
if (front < i - result[sum + n])
{
front = i - result[sum + n];
tail = i;
}
}
else
{
result[sum + n] = i;
}
}
if (tail == -1)
{
cout << "None";
}
else
{
cout << " Front " << (tail - front + 1) << " Tail " << tail;
}
}
};
int main()
{
SubArraySum task = SubArraySum();
// Case 1
// Define the array of (0,1) elements
int arr1[] =
{
1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0
};
int n = sizeof(arr1) / sizeof(arr1[0]);
task.zeroSumSubarray(arr1, n);
// Case 2
// Define the array of (0,1) elements
int arr2[] =
{
1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 1
};
n = sizeof(arr2) / sizeof(arr2[0]);
task.zeroSumSubarray(arr2, n);
return 0;
}
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
// Include namespace system
using System;
using System.Collections.Generic;
/*
C# program
Largest subarray with equal number of 0s and 1s
*/
public class SubArraySum
{
// This function are displaying given array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
// Find the subarray of equal number of 0s and 1s
public void zeroSumSubarray(int[] arr, int n)
{
// Display given array elements
Console.Write("\n Array :");
display(arr, n);
int front = -1;
int tail = -1;
Dictionary < int, int > result = new Dictionary < int, int > ();
int sum = 0;
int i = 0;
// Execute loop through by size of array elements
for (i = 0; i < n; ++i)
{
if (arr[i] == 1)
{
sum += 1;
}
else if (arr[i] == 0)
{
sum -= 1;
}
else
{
// When array contains another number
return;
}
if (sum == 0)
{
front = i + 1;
tail = i;
}
if (result.ContainsKey(sum + n))
{
if (front < i - result[sum + n])
{
front = i - result[sum + n];
tail = i;
}
}
else
{
result.Add(sum + n, i);
}
}
if (tail == -1)
{
Console.Write("None");
}
else
{
Console.Write(" Front " + (tail - front + 1) + " Tail " + tail);
}
}
public static void Main(String[] args)
{
SubArraySum task = new SubArraySum();
// Case 1
// Define the array of (0,1) elements
int[] arr1 = {
1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0
};
int n = arr1.Length;
task.zeroSumSubarray(arr1, n);
// Case 2
// Define the array of (0,1) elements
int[] arr2 = {
1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 1
};
n = arr2.Length;
task.zeroSumSubarray(arr2, n);
}
}
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
<?php
/*
Php program
Largest subarray with equal number of 0s and 1s
*/
class SubArraySum
{
// This function are displaying given array elements
public function display( & $arr, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo " ". $arr[$i];
}
echo "\n";
}
// Find the subarray of equal number of 0s and 1s
public function zeroSumSubarray( & $arr, $n)
{
// Display given array elements
echo "\n Array :";
$this->display($arr, $n);
$front = -1;
$tail = -1;
$result = array();
$sum = 0;
$i = 0;
// Execute loop through by size of array elements
for ($i = 0; $i < $n; ++$i)
{
if ($arr[$i] == 1)
{
$sum += 1;
}
else if ($arr[$i] == 0)
{
$sum -= 1;
}
else
{
// When array contains another number
return;
}
if ($sum == 0)
{
$front = $i + 1;
$tail = $i;
}
if (array_key_exists($sum + $n, $result))
{
if ($front < $i - $result[$sum + $n])
{
$front = $i - $result[$sum + $n];
$tail = $i;
}
}
else
{
$result[$sum + $n] = $i;
}
}
if ($tail == -1)
{
echo "None";
}
else
{
echo " Front ". ($tail - $front + 1) ." Tail ". $tail;
}
}
}
function main()
{
$task = new SubArraySum();
// Case 1
// Define the array of (0,1) elements
$arr1 = array(1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0);
$n = count($arr1);
$task->zeroSumSubarray($arr1, $n);
// Case 2
// Define the array of (0,1) elements
$arr2 = array(1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1);
$n = count($arr2);
$task->zeroSumSubarray($arr2, $n);
}
main();
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
/*
Node Js program
Largest subarray with equal number of 0s and 1s
*/
class SubArraySum
{
// This function are displaying given array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
// Find the subarray of equal number of 0s and 1s
zeroSumSubarray(arr, n)
{
// Display given array elements
process.stdout.write("\n Array :");
this.display(arr, n);
var front = -1;
var tail = -1;
var result = new Map();
var sum = 0;
var i = 0;
// Execute loop through by size of array elements
for (i = 0; i < n; ++i)
{
if (arr[i] == 1)
{
sum += 1;
}
else if (arr[i] == 0)
{
sum -= 1;
}
else
{
return;
}
if (sum == 0)
{
front = i + 1;
tail = i;
}
if (result.has(sum + n))
{
if (front < i - result.get(sum + n))
{
front = i - result.get(sum + n);
tail = i;
}
}
else
{
result.set(sum + n, i);
}
}
if (tail == -1)
{
process.stdout.write("None");
}
else
{
process.stdout.write(" Front " + (tail - front + 1) + " Tail " + tail);
}
}
}
function main()
{
var task = new SubArraySum();
// Case 1
// Define the array of (0,1) elements
var arr1 = [1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0];
var n = arr1.length;
task.zeroSumSubarray(arr1, n);
// Case 2
// Define the array of (0,1) elements
var arr2 = [1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1];
n = arr2.length;
task.zeroSumSubarray(arr2, n);
}
main();
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
#
# Python 3 program
# Largest subarray with equal number of 0s and 1s
class SubArraySum :
# This function are displaying given list elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print(end = "\n")
# Find the sublist of equal number of 0s and 1s
def zeroSumSubarray(self, arr, n) :
# Display given list elements
print("\n Array :", end = "")
self.display(arr, n)
front = -1
tail = -1
result = dict()
sum = 0
i = 0
# Execute loop through by size of list elements
while (i < n) :
if (arr[i] == 1) :
sum += 1
elif(arr[i] == 0) :
sum -= 1
else :
return
if (sum == 0) :
front = i + 1
tail = i
if (sum + n) in result.keys() :
if (front < i - result.get(sum + n)) :
front = i - result.get(sum + n)
tail = i
else :
result[sum + n] = i
i += 1
if (tail == -1) :
print("None", end = "")
else :
print(" Front ", (tail - front + 1) ," Tail ", tail, end = "")
def main() :
task = SubArraySum()
# Case 1
# Define the list of (0,1) elements
arr1 = [1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0]
n = len(arr1)
task.zeroSumSubarray(arr1, n)
# Case 2
# Define the list of (0,1) elements
arr2 = [1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1]
n = len(arr2)
task.zeroSumSubarray(arr2, n)
if __name__ == "__main__": main()
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
#
# Ruby program
# Largest subarray with equal number of 0s and 1s
class SubArraySum
# This function are displaying given array elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
# Find the subarray of equal number of 0s and 1s
def zeroSumSubarray(arr, n)
# Display given array elements
print("\n Array :")
self.display(arr, n)
front = -1
tail = -1
result = Hash.new
sum = 0
i = 0
# Execute loop through by size of array elements
while (i < n)
if (arr[i] == 1)
sum += 1
elsif(arr[i] == 0)
sum -= 1
else
# When array contains another number
return
end
if (sum == 0)
front = i + 1
tail = i
end
if (result.key?(sum + n))
if (front < i - result[sum + n])
front = i - result[sum + n]
tail = i
end
else
result[sum + n] = i
end
i += 1
end
if (tail == -1)
print("None")
else
print(" Front ", (tail - front + 1) ," Tail ", tail)
end
end
end
def main()
task = SubArraySum.new()
# Case 1
# Define the array of (0,1) elements
arr1 = [1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0]
n = arr1.length
task.zeroSumSubarray(arr1, n)
# Case 2
# Define the array of (0,1) elements
arr2 = [1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1]
n = arr2.length
task.zeroSumSubarray(arr2, n)
end
main()
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
import scala.collection.mutable._;
/*
Scala program
Largest subarray with equal number of 0s and 1s
*/
class SubArraySum
{
// This function are displaying given array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
// Find the subarray of equal number of 0s and 1s
def zeroSumSubarray(arr: Array[Int], n: Int): Unit = {
// Display given array elements
print("\n Array :");
this.display(arr, n);
var front: Int = -1;
var tail: Int = -1;
var result : HashMap[Int,Int] = HashMap();
var sum: Int = 0;
var i: Int = 0;
// Execute loop through by size of array elements
while (i < n)
{
if (arr(i) == 1)
{
sum += 1;
}
else if (arr(i) == 0)
{
sum -= 1;
}
else
{
// When array contains another number
return;
}
if (sum == 0)
{
front = i + 1;
tail = i;
}
if (result.contains(sum + n))
{
if (front < i - result.get(sum + n).get)
{
front = i - result.get(sum + n).get;
tail = i;
}
}
else
{
result.addOne(sum + n, i);
}
i += 1;
}
if (tail == -1)
{
print("None");
}
else
{
print(" Front " + (tail - front + 1) + " Tail " + tail);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubArraySum = new SubArraySum();
// Case 1
// Define the array of (0,1) elements
var arr1: Array[Int] = Array(1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0);
var n: Int = arr1.length;
task.zeroSumSubarray(arr1, n);
// Case 2
// Define the array of (0,1) elements
var arr2: Array[Int] = Array(1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1);
n = arr2.length;
task.zeroSumSubarray(arr2, n);
}
}
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
/*
Swift 4 program
Largest subarray with equal number of 0s and 1s
*/
class SubArraySum
{
// This function are displaying given array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Find the subarray of equal number of 0s and 1s
func zeroSumSubarray(_ arr: [Int], _ n: Int)
{
// Display given array elements
print("\n Array :", terminator: "");
self.display(arr, n);
var front: Int = -1;
var tail: Int = -1;
var result = [Int: Int]();
var sum: Int = 0;
var i: Int = 0;
// Execute loop through by size of array elements
while (i < n)
{
if (arr[i] == 1)
{
sum += 1;
}
// When array contains another number
else if (arr[i] == 0)
{
sum -= 1;
}
else
{
return;
}
if (sum == 0)
{
front = i + 1;
tail = i;
}
if (result.keys.contains(sum + n))
{
if (front < i - result[sum + n]!)
{
front = i - result[sum + n]!;
tail = i;
}
}
else
{
result[sum + n] = i;
}
i += 1;
}
if (tail == -1)
{
print("None", terminator: "");
}
else
{
print(" Front ", (tail - front + 1) ," Tail ", tail, terminator: "");
}
}
}
func main()
{
let task: SubArraySum = SubArraySum();
// Case 1
// Define the array of (0,1) elements
let arr1: [Int] = [1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0];
var n: Int = arr1.count;
task.zeroSumSubarray(arr1, n);
// Case 2
// Define the array of (0,1) elements
let arr2: [Int] = [1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1];
n = arr2.count;
task.zeroSumSubarray(arr2, n);
}
main();
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
/*
Kotlin program
Largest subarray with equal number of 0s and 1s
*/
class SubArraySum
{
// This function are displaying given array elements
fun display(arr: Array < Int > , size: Int): Unit
{
var i: Int = 0;
while (i < size)
{
print(" " + arr[i]);
i += 1;
}
print("\n");
}
// Find the subarray of equal number of 0s and 1s
fun zeroSumSubarray(arr: Array < Int > , n: Int): Unit
{
// Display given array elements
print("\n Array :");
this.display(arr, n);
var front: Int = -1;
var tail: Int = -1;
var result:HashMap<Int,Int> = HashMap<Int,Int>();
var sum: Int = 0;
var i: Int = 0;
// Execute loop through by size of array elements
while (i < n)
{
if (arr[i] == 1)
{
sum += 1;
}
// When array contains another number
else if (arr[i] == 0)
{
sum -= 1;
}
else
{
return;
}
if (sum == 0)
{
front = i + 1;
tail = i;
}
if (result.containsKey(sum + n))
{
if (front < i - result.getValue(sum + n))
{
front = i - result.getValue(sum + n);
tail = i;
}
}
else
{
result.put(sum + n, i);
}
i += 1;
}
if (tail == -1)
{
print("None");
}
else
{
print(" Front " + (tail - front + 1) + " Tail " + tail);
}
}
}
fun main(args: Array < String > ): Unit
{
var task: SubArraySum = SubArraySum();
// Case 1
// Define the array of (0,1) elements
var arr1: Array < Int > = arrayOf(1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0);
var n: Int = arr1.count();
task.zeroSumSubarray(arr1, n);
// Case 2
// Define the array of (0,1) elements
var arr2: Array < Int > = arrayOf(1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1);
n = arr2.count();
task.zeroSumSubarray(arr2, n);
}
Output
Array : 1 0 1 1 0 1 1 1 1 0 0 0
Front 4 Tail 11
Array : 1 0 1 1 1 1 0 1 1 0 0 1 1
Front 5 Tail 10
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