Skip to main content

Length of longest Subarray with equal number of odd and even elements

Given an array of integer elements, Our goal is to find the length of longest subarray which contain same number of even and odd elements. For example.


Input arr[] = [4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 5]
Output      =  4
Subarray [1 , 6 , 0 , 9] Here 2 even [1,9] and 2 odd [6,0]

Similar way find the length of subarray which are longest length of equal number of even and odd number.

Here given code implementation process.

// Java program for
// Length of longest Subarray with equal number of odd and even elements
import java.util.HashMap;
public class Subarray
{
	// Returns the maximum value of a and b
	public int max(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	// Return absolute value
	public int abs(int a)
	{
		if (a < 0)
		{
			return -a;
		}
		return a;
	}
	public int longestSubarray(int arr[], int n)
	{
		int sum = 0;
		int length = 0;
		// Use to store value of key and value pair
		// key indicate current sum of even and odd elements 
		// and values indicate index of current element
		HashMap < Integer, Integer > record = 
          new HashMap < Integer, Integer > ();
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] % 2 == 0)
			{
				// When element is even
				sum++;
			}
			else
			{
				// When element is odd
				sum--;
			}
			if (sum == 0)
			{
				length = max(length, i + 1);
			}
			if (!record.containsKey(sum))
			{
				// Add new key and value pair
				record.put(sum, i);
			}
			else
			{
				// Get new length
				// Using max of current index and record value
				length = max(sum, abs(i - record.get(sum)));
			}
		}
		// Return the calculated result
		return length;
	}
	public static void main(String[] args)
	{
		Subarray task = new Subarray();
		// Inputs
		int[] arr = {
			4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 5
		};
		// Get the length
		int n = arr.length;
		int result = task.longestSubarray(arr, n);
		// Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
		// [1 , 6 , 0 , 9]
		// Output : 4 
		System.out.println(" Result : " + result);
	}
}

Output

 Result : 4
// Include header file
#include <iostream>

#include <unordered_map>

using namespace std;
class Subarray
{
	public:
		// Returns the maximum value of a and b
		int max(int a, int b)
		{
			if (a > b)
			{
				return a;
			}
			return b;
		}
	// Return absolute value
	int abs(int a)
	{
		if (a < 0)
		{
			return -a;
		}
		return a;
	}
	int longestSubarray(int arr[], int n)
	{
		int sum = 0;
		int length = 0;
		// Use to store value of key and value pair
		// key indicate current sum of even and odd elements 
		// and values indicate index of current element
		unordered_map < int, int > record;
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] % 2 == 0)
			{
				// When element is even
				sum++;
			}
			else
			{
				// When element is odd
				sum--;
			}
			if (sum == 0)
			{
				length = this->max(length, i + 1);
			}
			if (record.find(sum) == record.end())
			{
				// Add new key and value pair
				record[sum] = i;
			}
			else
			{
				// Get new length
				// Using max of current index and record value
				length = this->max(sum, this->abs(i - record[sum]));
			}
		}
		// Return the calculated result
		return length;
	}
};
int main()
{
	Subarray *task = new Subarray();
	// Inputs
	int arr[] = {
		4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 5
	};
	// Get the length
	int n = sizeof(arr) / sizeof(arr[0]);
	int result = task->longestSubarray(arr, n);
	// Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
	// [1 , 6 , 0 , 9]
	// Output : 4 
	cout << " Result : " << result << endl;
	return 0;
}

Output

 Result : 4
// Include namespace system
using System;
using System.Collections.Generic;
using System.Collections;
namespace KalkiCode
{
	public class Subarray
	{
		// Returns the maximum value of a and b
		public int max(int a, int b)
		{
			if (a > b)
			{
				return a;
			}
			return b;
		}
		// Return absolute value
		public int abs(int a)
		{
			if (a < 0)
			{
				return -a;
			}
			return a;
		}
		public int longestSubarray(int[] arr, int n)
		{
			var sum = 0;
			var length = 0;
			// Use to store value of key and value pair
			// key indicate current sum of even and odd elements 
			// and values indicate index of current element
			var record = new Dictionary < int , int > ();
			for (var i = 0; i < n; ++i)
			{
				if (arr[i] % 2 == 0)
				{
					// When element is even
					sum++;
				}
				else
				{
					// When element is odd
					sum--;
				}
				if (sum == 0)
				{
					length = this.max(length, i + 1);
				}
				if (!record.ContainsKey(sum))
				{
					// Add new key and value pair
					record[sum] = i;
				}
				else
				{
					// Get new length
					// Using max of current index and record value
					length = this.max(sum, this.abs(i - record[sum]));
				}
			}
			// Return the calculated result
			return length;
		}
		public static void Main(String[] args)
		{
			var task = new Subarray();
			// Inputs
			int[] arr = {
				4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 5
			};
			// Get the length
			var n = arr.Length;
			var result = task.longestSubarray(arr, n);
			// Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
			// [1 , 6 , 0 , 9]
			// Output : 4 
			Console.WriteLine(" Result : " + result.ToString());
		}
	}
}

Output

 Result : 4
<?php
// Php program for
// Length of longest Subarray with equal number of odd and even elements
class Subarray
{
	// Returns the maximum value of a and b
	public	function max($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	// Return absolute value
	public	function abs($a)
	{
		if ($a < 0)
		{
			return -$a;
		}
		return $a;
	}
	public	function longestSubarray($arr, $n)
	{
		$sum = 0;
		$length = 0;
		// Use to store value of key and value pair
		// key indicate current sum of even and odd elements 
		// and values indicate index of current element
		$record = array();
		for ($i = 0; $i < $n; ++$i)
		{
			if ($arr[$i] % 2 == 0)
			{
				// When element is even
				$sum++;
			}
			else
			{
				// When element is odd
				$sum--;
			}
			if ($sum == 0)
			{
				$length = $this->max($length, $i + 1);
			}
			if (!array_key_exists($sum, $record))
			{
				// Add new key and value pair
				$record[$sum] = $i;
			}
			else
			{
				// Get new length
				// Using max of current index and record value
				$length = $this->max($sum, $this->abs($i - $record[$sum]));
			}
		}
		// Return the calculated result
		return $length;
	}
	public static
	function main($args)
	{
		$task = new Subarray();
		// Inputs
		$arr = array(4, 2, 1, 6, 0, 9, 2, 8, 4, 5);
		// Get the length
		$n = count($arr);
		$result = $task->longestSubarray($arr, $n);
		// Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
		// [1 , 6 , 0 , 9]
		// Output : 4 
		printf("%s\n", " Result : ".strval($result));
	}
}
Subarray::main(array());

Output

 Result : 4
// Node JS program for
// Length of longest Subarray with equal number of odd and even elements
class Subarray
{
	// Returns the maximum value of a and b
	max(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	// Return absolute value
	abs(a)
	{
		if (a < 0)
		{
			return -a;
		}
		return a;
	}
	longestSubarray(arr, n)
	{
		var sum = 0;
		var length = 0;
		// Use to store value of key and value pair
		// key indicate current sum of even and odd elements 
		// and values indicate index of current element
		var record = new Map();
		for (var i = 0; i < n; ++i)
		{
			if (arr[i] % 2 == 0)
			{
				// When element is even
				sum++;
			}
			else
			{
				// When element is odd
				sum--;
			}
			if (sum == 0)
			{
				length = this.max(length, i + 1);
			}
			if (!record.has(sum))
			{
				// Add new key and value pair
				record.set(sum, i);
			}
			else
			{
				// Get new length
				// Using max of current index and record value
				length = this.max(sum, this.abs(i - record.get(sum)));
			}
		}
		// Return the calculated result
		return length;
	}
}

function main()
{
	var task = new Subarray();
	// Inputs
	var arr = [4, 2, 1, 6, 0, 9, 2, 8, 4, 5];
	// Get the length
	var n = arr.length;
	var result = task.longestSubarray(arr, n);
	// Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
	// [1 , 6 , 0 , 9]
	// Output : 4 
	console.log(" Result : " + result);
}
// Start program execution
main();

Output

 Result : 4
#  Python 3 program for
#  Length of longest Subarray with equal number of odd and even elements
class Subarray :
	#  Returns the maximum value of a and b
	def max(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	#  Return absolute value
	def abs(self, a) :
		if (a < 0) :
			return -a
		
		return a
	
	def longestSubarray(self, arr, n) :
		sum = 0
		length = 0
		#  Use to store value of key and value pair
		#  key indicate current sum of even and odd elements 
		#  and values indicate index of current element
		record = dict()
		i = 0
		while (i < n) :
			if (arr[i] % 2 == 0) :
				#  When element is even
				sum += 1
			else :
				#  When element is odd
				sum -= 1
			
			if (sum == 0) :
				length = self.max(length, i + 1)
			
			if (not(sum in record.keys())) :
				#  Add new key and value pair
				record[sum] = i
			else :
				#  Get new length
				#  Using max of current index and record value
				length = self.max(sum, self.abs(i - record.get(sum)))
			
			i += 1
		
		#  Return the calculated result
		return length
	

def main() :
	task = Subarray()
	#  Inputs
	arr = [4, 2, 1, 6, 0, 9, 2, 8, 4, 5]
	#  Get the length
	n = len(arr)
	result = task.longestSubarray(arr, n)
	#  Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
	#  [1 , 6 , 0 , 9]
	#  Output : 4 
	print(" Result : ", result)

if __name__ == "__main__": main()

Output

 Result :  4
#  Ruby program for
#  Length of longest Subarray with equal number of odd and even elements
class Subarray 
	#  Returns the maximum value of a and b
	def max(a, b) 
		if (a > b) 
			return a
		end
		return b
	end

	#  Return absolute value
	def abs(a) 
		if (a < 0) 
			return -a
		end
		return a
	end

	def longestSubarray(arr, n) 
		sum = 0
		length = 0
		#  Use to store value of key and value pair
		#  key indicate current sum of even and odd elements 
		#  and values indicate index of current element
		record = Hash.new()
		i = 0
		while (i < n) 
			if (arr[i] % 2 == 0) 
				#  When element is even
				sum += 1
			else
 
				#  When element is odd
				sum -= 1
			end

			if (sum == 0) 
				length = self.max(length, i + 1)
			end

			if (!record.key?(sum)) 
				#  Add new key and value pair
				record[sum] = i
			else
 
				#  Get new length
				#  Using max of current index and record value
				length = self.max(sum, self.abs(i - record[sum]))
			end

			i += 1
		end

		#  Return the calculated result
		return length
	end

end

def main() 
	task = Subarray.new()
	#  Inputs
	arr = [4, 2, 1, 6, 0, 9, 2, 8, 4, 5]
	#  Get the length
	n = arr.length
	result = task.longestSubarray(arr, n)
	#  Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
	#  [1 , 6 , 0 , 9]
	#  Output : 4 
	print(" Result : ", result, "\n")
end

main()

Output

 Result : 4

import scala.collection.mutable._;
// Scala program for
// Length of longest Subarray with equal number of odd and even elements
class Subarray()
{
	// Returns the maximum value of a and b
	def max(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	// Return absolute value
	def abs(a: Int): Int = {
		if (a < 0)
		{
			return -a;
		}
		return a;
	}
	def longestSubarray(arr: Array[Int], n: Int): Int = {
		var sum: Int = 0;
		var length: Int = 0;
		// Use to store value of key and value pair
		// key indicate current sum of even and odd elements 
		// and values indicate index of current element
		var record: HashMap[Int, Int] = new HashMap[Int, Int]();
		var i: Int = 0;
		while (i < n)
		{
			if (arr(i) % 2 == 0)
			{
				// When element is even
				sum += 1;
			}
			else
			{
				// When element is odd
				sum -= 1;
			}
			if (sum == 0)
			{
				length = max(length, i + 1);
			}
			if (!record.contains(sum))
			{
				// Add new key and value pair
				record.addOne(sum, i);
			}
			else
			{
				// Get new length
				// Using max of current index and record value
				length = max(sum, abs(i - record.get(sum).get));
			}
			i += 1;
		}
		// Return the calculated result
		return length;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subarray = new Subarray();
		// Inputs
		var arr: Array[Int] = Array(4, 2, 1, 6, 0, 9, 2, 8, 4, 5);
		// Get the length
		var n: Int = arr.length;
		var result: Int = task.longestSubarray(arr, n);
		// Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
		// [1 , 6 , 0 , 9]
		// Output : 4 
		println(" Result : " + result);
	}
}

Output

 Result : 4
import Foundation;
// Swift 4 program for
// Length of longest Subarray with equal number of odd and even elements
class Subarray
{
	// Returns the maximum value of a and b
	func max(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	// Return absolute value
	func abs(_ a: Int) -> Int
	{
		if (a < 0)
		{
			return -a;
		}
		return a;
	}
	func longestSubarray(_ arr: [Int], _ n: Int) -> Int
	{
		var sum: Int = 0;
		var length: Int = 0;
		// Use to store value of key and value pair
		// key indicate current sum of even and odd elements 
		// and values indicate index of current element
		var record: [Int : Int] = [Int : Int]();
		var i: Int = 0;
		while (i < n)
		{
			if (arr[i] % 2 == 0)
			{
				// When element is even
				sum += 1;
			}
			else
			{
				// When element is odd
				sum -= 1;
			}
			if (sum == 0)
			{
				length = self.max(length, i + 1);
			}
			if (!record.keys.contains(sum))
			{
				// Add new key and value pair
				record[sum] = i;
			}
			else
			{
				// Get new length
				// Using max of current index and record value
				length = self.max(sum, self.abs(i - record[sum]!));
			}
			i += 1;
		}
		// Return the calculated result
		return length;
	}
}
func main()
{
	let task: Subarray = Subarray();
	// Inputs
	let arr: [Int] = [4, 2, 1, 6, 0, 9, 2, 8, 4, 5];
	// Get the length
	let n: Int = arr.count;
	let result: Int = task.longestSubarray(arr, n);
	// Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
	// [1 , 6 , 0 , 9]
	// Output : 4 
	print(" Result : ", result);
}
main();

Output

 Result :  4
// Kotlin program for
// Length of longest Subarray with equal number of odd and even elements
class Subarray
{
	// Returns the maximum value of a and b
	fun max(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	// Return absolute value
	fun abs(a: Int): Int
	{
		if (a < 0)
		{
			return -a;
		}
		return a;
	}
	fun longestSubarray(arr: Array < Int > , n: Int): Int
	{
		var sum: Int = 0;
		var length: Int = 0;
		// Use to store value of key and value pair
		// key indicate current sum of even and odd elements 
		// and values indicate index of current element
		var record: HashMap < Int, Int > = HashMap < Int, Int > ();
		var i: Int = 0;
		while (i < n)
		{
			if (arr[i] % 2 == 0)
			{
				// When element is even
				sum += 1;
			}
			else
			{
				// When element is odd
				sum -= 1;
			}
			if (sum == 0)
			{
				length = this.max(length, i + 1);
			}
			if (!record.containsKey(sum))
			{
				// Add new key and value pair
				record.put(sum, i);
			}
			else
			{
				// Get new length
				// Using max of current index and record value
				length = this.max(sum, this.abs(i - record.getValue(sum)));
			}
			i += 1;
		}
		// Return the calculated result
		return length;
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subarray = Subarray();
	// Inputs
	val arr: Array < Int > = arrayOf(4, 2, 1, 6, 0, 9, 2, 8, 4, 5);
	// Get the length
	val n: Int = arr.count();
	val result: Int = task.longestSubarray(arr, n);
	// Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
	// [1 , 6 , 0 , 9]
	// Output : 4 
	println(" Result : " + result);
}

Output

 Result : 4
// Kotlin program for
// Length of longest Subarray with equal number of odd and even elements
class Subarray
{
	// Returns the maximum value of a and b
	fun max(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	// Return absolute value
	fun abs(a: Int): Int
	{
		if (a < 0)
		{
			return -a;
		}
		return a;
	}
	fun longestSubarray(arr: Array < Int > , n: Int): Int
	{
		var sum: Int = 0;
		var length: Int = 0;
		// Use to store value of key and value pair
		// key indicate current sum of even and odd elements 
		// and values indicate index of current element
		var record: HashMap < Int, Int > = HashMap < Int, Int > ();
		var i: Int = 0;
		while (i < n)
		{
			if (arr[i] % 2 == 0)
			{
				// When element is even
				sum += 1;
			}
			else
			{
				// When element is odd
				sum -= 1;
			}
			if (sum == 0)
			{
				length = this.max(length, i + 1);
			}
			if (!record.containsKey(sum))
			{
				// Add new key and value pair
				record.put(sum, i);
			}
			else
			{
				// Get new length
				// Using max of current index and record value
				length = this.max(sum, this.abs(i - record.getValue(sum)));
			}
			i += 1;
		}
		// Return the calculated result
		return length;
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subarray = Subarray();
	// Inputs
	val arr: Array < Int > = arrayOf(4, 2, 1, 6, 0, 9, 2, 8, 4, 5);
	// Get the length
	val n: Int = arr.count();
	val result: Int = task.longestSubarray(arr, n);
	// Input : [ 4 , 2 , 1 , 6 , 0 , 9 , 2 , 8 , 4 , 59]
	// [1 , 6 , 0 , 9]
	// Output : 4 
	println(" Result : " + result);
}

Output

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