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