Dado un arreglo entero arr[] , la tarea es encontrar la longitud del subarreglo más largo con el mismo número de elementos pares e impares.
Ejemplos:
Entrada: array[] = {1, 2, 1, 2}
Salida: 4
Explicación:
Los subarreglos en la array dada son:
{{1}, {1, 2}, {1, 2, 1}, {1, 2 , 1, 2}, {2}, {2, 1}, {2, 1, 2}, {1}, {1, 2}, {2}}
donde la longitud del subarreglo más largo con el mismo número de elementos pares e impares es 4 – {1, 2, 1, 2}Entrada: arr[] = {12, 4, 7, 8, 9, 2, 11, 0, 2, 13}
Salida: 8
Enfoque ingenuo: la solución simple es considerar todos los subarreglos uno por uno y verificar el recuento de elementos pares e impares en el subarreglo y encontrar el máximo de esos subarreglos.
Complejidad del tiempo: O(N 2 )
Enfoque eficiente: la idea es considerar los elementos impares como 1 y los elementos pares como -1 y devolver la longitud del subarreglo más largo con la suma igual a 0. El subarreglo con una suma dada se puede encontrar usando este método.
Complejidad de tiempo: O(N)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the length
// of the longest sub-array with an
// equal number of odd and even elements
#include <bits/stdc++.h>
using namespace std;
// Function that returns the length of
// the longest sub-array with an equal
// number of odd and even elements
int maxSubarrayLength(int* A, int N)
{
// Initialize variable to store result
int maxLen = 0;
// Initialize variable to store sum
int curr_sum = 0;
// Create an empty map to store
// index of the sum
unordered_map<int, int> hash;
// Loop through the array
for (int i = 0; i < N; i++) {
if (A[i] % 2 == 0)
curr_sum -= 1;
else
curr_sum += 1;
// Check if number of even and
// odd elements are equal
if (curr_sum == 0)
maxLen = max(maxLen, i + 1);
// If curr_sum already exists in map
// we have a subarray with 0 sum, i.e,
// equal number of odd and even number
if (hash.find(curr_sum) != hash.end())
maxLen = max(maxLen,
i - hash[curr_sum]);
// Store the index of the sum
else
hash[curr_sum] = i;
}
return maxLen;
}
// Driver Code
int main()
{
int arr[] = { 12, 4, 7, 8, 9, 2,
11, 0, 2, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxSubarrayLength(arr, n);
return 0;
}
Java
// Java program to find the length
// of the longest sub-array with an
// equal number of odd and even elements
import java.util.*;
class GFG
{
// Function that returns the length of
// the longest sub-array with an equal
// number of odd and even elements
static int maxSubarrayLength(int []A, int N)
{
// Initialize variable to store result
int maxLen = 0;
// Initialize variable to store sum
int curr_sum = 0;
// Create an empty map to store
// index of the sum
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
// Loop through the array
for (int i = 0; i < N; i++)
{
if (A[i] % 2 == 0)
curr_sum -= 1;
else
curr_sum += 1;
// Check if number of even and
// odd elements are equal
if (curr_sum == 0)
maxLen = Math.max(maxLen, i + 1);
// If curr_sum already exists in map
// we have a subarray with 0 sum, i.e,
// equal number of odd and even number
if (hash.containsKey(curr_sum))
maxLen = Math.max(maxLen,
i - hash.get(curr_sum));
// Store the index of the sum
else {
hash.put(curr_sum, i);
}
}
return maxLen;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 12, 4, 7, 8, 9, 2,
11, 0, 2, 13 };
int n = arr.length;
System.out.print(maxSubarrayLength(arr, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the length
# of the longest sub-array with an
# equal number of odd and even elements
# Function that returns the length of
# the longest sub-array with an equal
# number of odd and even elements
def maxSubarrayLength(A, N) :
# Initialize variable to store result
maxLen = 0;
# Initialize variable to store sum
curr_sum = 0;
# Create an empty map to store
# index of the sum
hash = {};
# Loop through the array
for i in range(N) :
if (A[i] % 2 == 0) :
curr_sum -= 1;
else :
curr_sum += 1;
# Check if number of even and
# odd elements are equal
if (curr_sum == 0) :
maxLen = max(maxLen, i + 1);
# If curr_sum already exists in map
# we have a subarray with 0 sum, i.e,
# equal number of odd and even number
if curr_sum in hash :
maxLen = max(maxLen, i - hash[curr_sum]);
# Store the index of the sum
else :
hash[curr_sum] = i;
return maxLen;
# Driver Code
if __name__ == "__main__" :
arr = [ 12, 4, 7, 8, 9, 2, 11, 0, 2, 13 ];
n = len(arr);
print(maxSubarrayLength(arr, n));
# This code is contributed by AnkitRai01
C#
// C# program to find the length
// of the longest sub-array with an
// equal number of odd and even elements
using System;
using System.Collections.Generic;
class GFG
{
// Function that returns the length of
// the longest sub-array with an equal
// number of odd and even elements
static int maxSubarrayLength(int []A, int N)
{
// Initialize variable to store result
int maxLen = 0;
// Initialize variable to store sum
int curr_sum = 0;
// Create an empty map to store
// index of the sum
Dictionary<int, int> hash = new Dictionary<int, int>();
// Loop through the array
for (int i = 0; i < N; i++)
{
if (A[i] % 2 == 0)
curr_sum -= 1;
else
curr_sum += 1;
// Check if number of even and
// odd elements are equal
if (curr_sum == 0)
maxLen = Math.Max(maxLen, i + 1);
// If curr_sum already exists in map
// we have a subarray with 0 sum, i.e,
// equal number of odd and even number
if (hash.ContainsKey(curr_sum))
maxLen = Math.Max(maxLen,
i - hash[curr_sum]);
// Store the index of the sum
else {
hash.Add(curr_sum, i);
}
}
return maxLen;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 12, 4, 7, 8, 9, 2,
11, 0, 2, 13 };
int n = arr.Length;
Console.Write(maxSubarrayLength(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find the length
// of the longest sub-array with an
// equal number of odd and even elements
// Function that returns the length of
// the longest sub-array with an equal
// number of odd and even elements
function maxSubarrayLength(A, N)
{
// Initialize variable to store result
var maxLen = 0;
// Initialize variable to store sum
var curr_sum = 0;
// Create an empty map to store
// index of the sum
var hash = new Map();
// Loop through the array
for (var i = 0; i < N; i++) {
if (A[i] % 2 == 0)
curr_sum -= 1;
else
curr_sum += 1;
// Check if number of even and
// odd elements are equal
if (curr_sum == 0)
maxLen = Math.max(maxLen, i + 1);
// If curr_sum already exists in map
// we have a subarray with 0 sum, i.e,
// equal number of odd and even number
if (hash.has(curr_sum))
maxLen = Math.max(maxLen,
i - hash.get(curr_sum));
// Store the index of the sum
else
hash.set(curr_sum, i);
}
return maxLen;
}
// Driver Code
var arr = [12, 4, 7, 8, 9, 2,
11, 0, 2, 13 ];
var n = arr.length;
document.write( maxSubarrayLength(arr, n));
</script>
Producción:
8
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA