Skip to main content

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
Last updated on by Kalkicode




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