Skip to main content

Find longest subarray with 0 sum

Here given code implementation process.

/*
    Java Program
    Find longest subarray with 0 sum
*/
import java.util.HashMap;
public class SubArray
{
	// Function which is display array elements
	public void display(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print("   " + arr[i]);
		}
	}
	// Returns the max value of given two numbersr
	public int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Find longest length subarray of zero sum in given array
	public void longestZeroSubarray(int[] arr, int size)
	{
		// Create an empty map
		HashMap < Integer, Integer > mp = new HashMap < Integer, Integer > ();
		// Define resultant variables
		int result = 0;
		int sum = 0;
		// iterate the loop through by array size
		for (int i = 0; i < size; i++)
		{
			// Add array element
			sum += arr[i];
			if (arr[i] == 0 && result == 0)
			{
				// When current element is zero and
				// result is zero
				result = 1;
			}
			if (sum == 0)
			{
				// When subarray sum is zero (0..i)
				result = i + 1;
			}
			if (mp.containsKey(sum))
			{
				// When sum exists 
				result = max(result, i - mp.get(sum));
			}
			else
			{
				mp.put(sum, i);
			}
		}
		// Display array elements
		display(arr, size);
		System.out.print("\n   Length of 0 sum subarray is  : ");
		if (result == 0)
		{
			// When no zero sum subarray exist
			System.out.print(" None \n");
		}
		else
		{
			System.out.print(" " + result);
		}
	}
	// Start execution process
	public static void main(String[] arg)
	{
		SubArray task = new SubArray();
		// Define array of integer elements
		int[] arr = {
			5 , 2 , 6 , -4 , 7 , -9 , 3 , 0 , -2 , 2
		};
		// Get number of element
		int size = arr.length;
		// Test
		task.longestZeroSubarray(arr, size);
	}
}

Output

   5   2   6   -4   7   -9   3   0   -2   2
   Length of 0 sum subarray is  :  4
// Include header file
#include <iostream>
#include <unordered_map>
using namespace std;
/*
    C++ Program
    Find longest subarray with 0 sum
*/
class SubArray
{
	public:
		// Function which is display array elements
		void display(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << "   " << arr[i];
			}
		}
	// Returns the max value of given two numbersr
	int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Find longest length subarray of zero sum in given array
	void longestZeroSubarray(int arr[], int size)
	{
		// Create an empty map
		unordered_map < int, int > mp;
		// Define resultant variables
		int result = 0;
		int sum = 0;
		// iterate the loop through by array size
		for (int i = 0; i < size; i++)
		{
			// Add array element
			sum += arr[i];
			if (arr[i] == 0 && result == 0)
			{
				// When current element is zero and
				// result is zero
				result = 1;
			}
			if (sum == 0)
			{
				// When subarray sum is zero (0..i)
				result = i + 1;
			}
			if (mp.find(sum) != mp.end())
			{
				// When sum exists
				result = this->max(result, i - mp[sum]);
			}
			else
			{
				mp[sum] = i;
			}
		}
		// Display array elements
		this->display(arr, size);
		cout << "\n   Length of 0 sum subarray is  : ";
		if (result == 0)
		{
			// When no zero sum subarray exist
			cout << " None \n";
		}
		else
		{
			cout << " " << result;
		}
	}
};
int main()
// Drive method
{
	SubArray task = SubArray();
	// Define array of integer elements
	int arr[] = {
		5 , 2 , 6 , -4 , 7 , -9 , 3 , 0 , -2 , 2
	};
	// Get number of element
	int size = sizeof(arr) / sizeof(arr[0]);
	// Test
	task.longestZeroSubarray(arr, size);
	return 0;
}

Output

   5   2   6   -4   7   -9   3   0   -2   2
   Length of 0 sum subarray is  :  4
// Include namespace system
using System;
using System.Collections.Generic;
/*
    C# Program
    Find longest subarray with 0 sum
*/
public class SubArray
{
	// Function which is display array elements
	public void display(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write("   " + arr[i]);
		}
	}
	// Returns the max value of given two numbersr
	public int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Find longest length subarray of zero sum in given array
	public void longestZeroSubarray(int[] arr, int size)
	{
		// Create an empty dictionary
		Dictionary < int, int > mp = new Dictionary < int, int > ();
		// Define resultant variables
		int result = 0;
		int sum = 0;
		// iterate the loop through by array size
		for (int i = 0; i < size; i++)
		{
			// Add array element
			sum += arr[i];
			if (arr[i] == 0 && result == 0)
			{
				// When current element is zero and
				// result is zero
				result = 1;
			}
			if (sum == 0)
			{
				// When subarray sum is zero (0..i)
				result = i + 1;
			}
			if (mp.ContainsKey(sum))
			{
				// When sum exists
				result = max(result, i - mp[sum]);
			}
			else
			{
				mp.Add(sum, i);
			}
		}
		// Display array elements
		display(arr, size);
		Console.Write("\n   Length of 0 sum subarray is  : ");
		if (result == 0)
		{
			// When no zero sum subarray exist
			Console.Write(" None \n");
		}
		else
		{
			Console.Write(" " + result);
		}
	}
	// Drive method
	public static void Main(String[] arg)
	{
		SubArray task = new SubArray();
		// Define array of integer elements
		int[] arr = {
			5 , 2 , 6 , -4 , 7 , -9 , 3 , 0 , -2 , 2
		};
		// Get number of element
		int size = arr.Length;
		// Test
		task.longestZeroSubarray(arr, size);
	}
}

Output

   5   2   6   -4   7   -9   3   0   -2   2
   Length of 0 sum subarray is  :  4
<?php
/*
    Php Program
    Find longest subarray with 0 sum
*/
class SubArray
{
	// Function which is display array elements
	public	function display($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo "   ". $arr[$i];
		}
	}
	// Returns the max value of given two numbersr
	public	function max($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	// Find longest length subarray of zero sum in given array
	public	function longestZeroSubarray($arr, $size)
	{
		// Create an empty array
		$mp = array();
		// Define resultant variables
		$result = 0;
		$sum = 0;
		// iterate the loop through by array size
		for ($i = 0; $i < $size; $i++)
		{
			// Add array element
			$sum += $arr[$i];
			if ($arr[$i] == 0 && $result == 0)
			{
				// When current element is zero and
				// result is zero
				$result = 1;
			}
			if ($sum == 0)
			{
				// When subarray sum is zero (0..i)
				$result = $i + 1;
			}
			if (array_key_exists($sum, $mp))
			{
				// When sum exists
				$result = $this->max($result, $i - $mp[$sum]);
			}
			else
			{
				$mp[$sum] = $i;
			}
		}
		// Display array elements
		$this->display($arr, $size);
		echo "\n   Length of 0 sum subarray is  : ";
		if ($result == 0)
		{
			// When no zero sum subarray exist
			echo " None \n";
		}
		else
		{
			echo " ". $result;
		}
	}
}

function main()
// Drive method
{
	$task = new SubArray();
	// Define array of integer elements
	$arr = array(5, 2, 6, -4, 7, -9, 3, 0, -2, 2);
	// Get number of element
	$size = count($arr);
	// Test
	$task->longestZeroSubarray($arr, $size);
}
main();

Output

   5   2   6   -4   7   -9   3   0   -2   2
   Length of 0 sum subarray is  :  4
/*
    Node Js Program
    Find longest subarray with 0 sum
*/
class SubArray
{
	// Function which is display array elements
	display(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write("   " + arr[i]);
		}
	}
	// Returns the max value of given two numbersr
	max(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Find longest length subarray of zero sum in given array
	longestZeroSubarray(arr, size)
	{
		// Create an empty map
		var mp = new Map();
		// Define resultant variables
		var result = 0;
		var sum = 0;
		// iterate the loop through by array size
		for (var i = 0; i < size; i++)
		{
			// Add array element
			sum += arr[i];
			if (arr[i] == 0 && result == 0)
			{
				// When current element is zero and
				// result is zero
				result = 1;
			}
			if (sum == 0)
			{
				// When subarray sum is zero (0..i)
				result = i + 1;
			}
			if (mp.has(sum))
			{
				// When sum exists
				result = this.max(result, i - mp.get(sum));
			}
			else
			{
				mp.set(sum, i);
			}
		}
		// Display array elements
		this.display(arr, size);
		process.stdout.write("\n   Length of 0 sum subarray is  : ");
		if (result == 0)
		{
			// When no zero sum subarray exist
			process.stdout.write(" None \n");
		}
		else
		{
			process.stdout.write(" " + result);
		}
	}
}

function main()
// Drive method
{
	var task = new SubArray();
	// Define array of integer elements
	var arr = [5, 2, 6, -4, 7, -9, 3, 0, -2, 2];
	// Get number of element
	var size = arr.length;
	// Test
	task.longestZeroSubarray(arr, size);
}
main();

Output

   5   2   6   -4   7   -9   3   0   -2   2
   Length of 0 sum subarray is  :  4
# Python 3 Program
# Find longest subarray with 0 sum

class SubArray :
	#  Function which is display list elements
	def display(self, arr, n) :
		i = 0
		while (i < n) :
			print("  ", arr[i], end = "")
			i += 1
		
	
	#  Returns the max value of given two numbersr
	def max(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	#  Find longest length sublist of zero sum in given list
	def longestZeroSubarray(self, arr, size) :
		#  Create an empty dic
		mp = dict()
		#  Define resultant variables
		result = 0
		sum = 0
		#  iterate the loop through by list size
		i = 0
		while (i < size) :
			#  Add list element
			sum += arr[i]
			if (arr[i] == 0 and result == 0) :
				#  When current element is zero and
				#  result is zero
				result = 1
			
			if (sum == 0) :
				#  When sublist sum is zero (0..i)
				result = i + 1
			
			if (sum in mp.keys()) :
				#  When sum exists
				result = self.max(result, i - mp.get(sum))
			else :
				mp[sum] = i
			
			i += 1
		
		#  Display list elements
		self.display(arr, size)
		print("\n   Length of 0 sum subarray is  : ", end = "")
		if (result == 0) :
			#  When no zero sum sublist exist
			print(" None ")
		else :
			print(" ", result, end = "")
		
	

def main() :
	task = SubArray()
	#  Define list of integer elements
	arr = [5, 2, 6, -4, 7, -9, 3, 0, -2, 2]
	#  Get number of element
	size = len(arr)
	#  Test
	task.longestZeroSubarray(arr, size)

if __name__ == "__main__": main()

Output

   5   2   6   -4   7   -9   3   0   -2   2
   Length of 0 sum subarray is  :   4
#  Ruby Program
#  Find longest subarray with 0 sum

class SubArray 
	#  Function which is display array elements
	def display(arr, n) 
		i = 0
		while (i < n) 
			print("   ", arr[i])
			i += 1
		end

	end

	#  Returns the max value of given two numbersr
	def max(a, b) 
		if (a > b) 
			return a
		else 
			return b
		end

	end

	#  Find longest length subarray of zero sum in given array
	def longestZeroSubarray(arr, size) 
		#  Create an empty Hash
		mp = Hash.new ()
		#  Define resultant variables
		result = 0
		sum = 0
		#  iterate the loop through by array size
		i = 0
		while (i < size) 
			#  Add array element
			sum += arr[i]
			if (arr[i] == 0 && result == 0) 
				#  When current element is zero and
				#  result is zero
				result = 1
			end

			if (sum == 0) 
				#  When subarray sum is zero (0..i)
				result = i + 1
			end

			if (mp.key?(sum)) 
				#  When sum exists
				result = self.max(result, i - mp[sum])
			else 
				mp[sum] = i
			end

			i += 1
		end

		#  Display array elements
		self.display(arr, size)
		print("\n   Length of 0 sum subarray is  : ")
		if (result == 0) 
			#  When no zero sum subarray exist
			print(" None \n")
		else 
			print(" ", result)
		end
	end
end

def main() 
	task = SubArray.new()
	#  Define array of integer elements
	arr = [5, 2, 6, -4, 7, -9, 3, 0, -2, 2]
	#  Get number of element
	size = arr.length
	#  Test
	task.longestZeroSubarray(arr, size)
end

main()

Output

   5   2   6   -4   7   -9   3   0   -2   2
   Length of 0 sum subarray is  :  4
import scala.collection.mutable._;
/*
    Scala Program
    Find longest subarray with 0 sum
*/
class SubArray
{
	// Function which is display array elements
	def display(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print("   " + arr(i));
			i += 1;
		}
	}
	// Returns the max value of given two numbersr
	def max(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Find longest length subarray of zero sum in given array
	def longestZeroSubarray(arr: Array[Int], size: Int): Unit = {
		// Create an empty map
		var mp: Map[Int, Int] = Map();
		// Define resultant variables
		var result: Int = 0;
		var sum: Int = 0;
		// iterate the loop through by array size
		var i: Int = 0;
		while (i < size)
		{
			// Add array element
			sum += arr(i);
			if (arr(i) == 0 && result == 0)
			{
				// When current element is zero and
				// result is zero
				result = 1;
			}
			if (sum == 0)
			{
				// When subarray sum is zero (0..i)
				result = i + 1;
			}
			if (mp.contains(sum))
			{
				// When sum exists
				result = this.max(result, i - mp.get(sum).get);
			}
			else
			{
				mp.addOne(sum, i);
			}
			i += 1;
		}
		// Display array elements
		this.display(arr, size);
		print("\n   Length of 0 sum subarray is  : ");
		if (result == 0)
		{
			// When no zero sum subarray exist
			print(" None \n");
		}
		else
		{
			print(" " + result);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: SubArray = new SubArray();
		// Define array of integer elements
		var arr: Array[Int] = Array(5, 2, 6, -4, 7, -9, 3, 0, -2, 2);
		// Get number of element
		var size: Int = arr.length;
		// Test
		task.longestZeroSubarray(arr, size);
	}
}

Output

   5   2   6   -4   7   -9   3   0   -2   2
   Length of 0 sum subarray is  :  4
import Foundation
/*
    Swift 4 Program
    Find longest subarray with 0 sum
*/
class SubArray
{
	// Function which is display array elements
	func display(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print("   ", arr[i], terminator: "");
			i += 1;
		}
	}
	// Returns the max value of given two numbersr
	func max(_ a: Int, _ b: Int)->Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Find longest length subarray of zero sum in given array
	func longestZeroSubarray(_ arr: [Int], _ size: Int)
	{
		// Create an empty dictionary
		var mp = [Int: Int]();
		// Define resultant variables
		var result: Int = 0;
		var sum: Int = 0;
		// iterate the loop through by array size
		var i: Int = 0;
		while (i < size)
		{
			// Add array element
			sum += arr[i];
			if (arr[i] == 0 && result == 0)
			{
				// When current element is zero and
				// result is zero
				result = 1;
			}
			if (sum == 0)
			{
				// When subarray sum is zero (0..i)
				result = i + 1;
			}
			if (mp.keys.contains(sum))
			{
				// When sum exists
				result = self.max(result, i - mp[sum]!);
			}
			else
			{
				mp[sum] = i;
			}
			i += 1;
		}
		// Display array elements
		self.display(arr, size);
		print("\n   Length of 0 sum subarray is  : ", terminator: "");
		if (result == 0)
		{
			// When no zero sum subarray exist
			print(" None ");
		}
		else
		{
			print(" ", result, terminator: "");
		}
	}
}
func main()
{
	let task: SubArray = SubArray();
	// Define array of integer elements
	let arr: [Int] = [5, 2, 6, -4, 7, -9, 3, 0, -2, 2];
	// Get number of element
	let size: Int = arr.count;
	// Test
	task.longestZeroSubarray(arr, size);
}
main();

Output

    5    2    6    -4    7    -9    3    0    -2    2
   Length of 0 sum subarray is  :   4
/*
    Kotlin Program
    Find longest subarray with 0 sum
*/
class SubArray
{
	// Function which is display array elements
	fun display(arr: Array <Int> , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print("   " + arr[i]);
			i += 1;
		}
	}
	// Returns the max value of given two numbersr
	fun max(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Find longest length subarray of zero sum in given array
	fun longestZeroSubarray(arr: Array < Int > , size: Int): Unit
	{
		// Create an empty map
		var mp = mutableMapOf<Int, Int>();
		// Define resultant variables
		var result: Int = 0;
		var sum: Int = 0;
		// iterate the loop through by array size
		var i: Int = 0;
		while (i < size)
		{
			// Add array element
			sum += arr[i];
			if (arr[i] == 0 && result == 0)
			{
				// When current element is zero and
				// result is zero
				result = 1;
			}
			if (sum == 0)
			{
				// When subarray sum is zero (0..i)
				result = i + 1;
			}
			if (mp.containsKey(sum))
			{
				// When sum exists
				result = this.max(result, i - mp.getValue(sum));
			}
			else
			{
				mp.put(sum, i);
			}
			i += 1;
		}
		// Display array elements
		this.display(arr, size);
		print("\n   Length of 0 sum subarray is  : ");
		if (result == 0)
		{
			// When no zero sum subarray exist
			print(" None \n");
		}
		else
		{
			print(" " + result);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: SubArray = SubArray();
	// Define array of integer elements
	var arr: Array < Int > = arrayOf(5, 2, 6, -4, 7, -9, 3, 0, -2, 2);
	// Get number of element
	var size: Int = arr.count();
	// Test
	task.longestZeroSubarray(arr, size);
}

Output

   5   2   6   -4   7   -9   3   0   -2   2
   Length of 0 sum subarray is  :  4
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