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