Dado un arreglo a[] de N enteros, la tarea es encontrar la longitud del subarreglo Par Impar Alternativo más largo presente en el arreglo.
Ejemplos:
Entrada: a[] = {1, 2, 3, 4, 5, 7, 9}
Salida: 5
Explicación:
El subarreglo {1, 2, 3, 4, 5} tiene elementos pares e impares alternos.
Entrada: a[] = {1, 3, 5}
Salida: 0
Explicación:
No es posible tal secuencia alterna.
Enfoque 1: enfoque ingenuo
Explicación: considere cada subarreglo y encuentre la longitud del subarreglo par e impar
C++
#include <iostream>
using namespace std;
// Function to find the longest subarray
int longestEvenOddSubarray(int a[], int n)
{
// Length of longest
// alternating subarray
int ans = 1;
// Iterate in the array
for (int i = 0; i < n ; i++) {
int cnt = 1;
// Iterate for every subarray
for (int j = i + 1; j < n; j++) {
if ((a[j - 1] % 2 == 0 && a[j] % 2 != 0)
|| (a[j - 1] % 2 != 0 && a[j] % 2 == 0))
cnt++;
else
break;
}
// store max count
ans = max(ans, cnt);
}
// Length of 'ans' can never be 1
// since even odd has to occur in pair or more
// so return 0 if ans = 1
if (ans == 1)
return 0;
return ans;
}
/* Driver code*/
int main()
{
int a[] = { 1, 2, 3, 4, 5, 7, 8};
int n = sizeof(a) / sizeof(a[0]);
cout << longestEvenOddSubarray(a, n);
return 0;
}
Java
// Java program for above approach
import java.io.*;
import java.util.ArrayList;
import java.util.List;
// Function to check if it is possible
// to make the array elements consecutive
public class GfG{
// Function to find the longest subarray
static int longestEvenOddSubarray(ArrayList<Integer>a, int n){
// Length of longest
// alternating subarray
int ans = 1;
// Iterate in the array
for (int i = 0; i < n ; i++) {
int cnt = 1;
// Iterate for every subarray
for (int j = i + 1; j < n; j++) {
if ((a.get(j - 1)% 2 == 0 && a.get(j) % 2 != 0)
|| (a.get(j - 1) % 2 != 0 && a.get(j) % 2 == 0))
cnt++;
else
break;
}
// store max count
ans = Math.max(ans, cnt);
}
//Length of 'ans' can never be 1
// since even odd has to occur in pair or more
// so return 0 if ans = 1
if (ans == 1)
return 0;
return ans;
}
// Drivers code
public static void main(String args[])
{
ArrayList<Integer>a = new ArrayList<Integer>(List.of(1, 2, 3, 4, 5, 7, 8 ));
int n = a.size();
System.out.println(longestEvenOddSubarray(a, n));
}
}
// This code is contributed by shinjanpatra
Python3
import math # Function to find the longest subarray def longestEvenOddSubarray(a, n): # Length of longest # alternating subarray ans = 1 # Iterate in the array for i in range(n): cnt = 1 # Iterate for every subarray for j in range(i + 1,n): if ((a[j - 1] % 2 == 0 and a[j] % 2 != 0) or (a[j - 1] % 2 != 0 and a[j] % 2 == 0)): cnt = cnt+1 else: break # store max count ans = max(ans, cnt) # Length of 'longest' can never be 1 since # even odd has to occur in pair or more # so return 0 if longest = 1 if(ans == 1): return 0 return ans # Driver code a = [ 1, 2, 3, 4, 5, 7, 8 ] n = len(a) print(longestEvenOddSubarray(a, n)) # This code is contributed by shinjanpatra.
Javascript
<script>
// Function to find the longest subarray
function longestEvenOddSubarray(a, n)
{
// Length of longest
// alternating subarray
let ans = 1;
// Iterate in the array
for (let i = 0; i < n ; i++) {
let cnt = 1;
// Iterate for every subarray
for (let j = i + 1; j < n; j++) {
if ((a[j - 1] % 2 == 0 && a[j] % 2 != 0)
|| (a[j - 1] % 2 != 0 && a[j] % 2 == 0))
cnt++;
else
break;
}
// store max count
ans = Math.max(ans, cnt);
}
// Length of 'ans' can never be 1
// since even odd has to occur in pair or more
// so return 0 if ans = 1
if (ans == 1)
return 0;
return ans;
}
/* Driver code*/
let a = [ 1, 2, 3, 4, 5, 7, 8 ];
let n = a.length;
document.write(longestEvenOddSubarray(a, n),"</br>");
// This code is contributed by shinjanpatra.
</script>
Producción
5
Enfoque 2: para resolver el problema mencionado anteriormente, debemos observar que la suma de dos números pares es par, la suma de dos números impares es par, pero la suma de un número par y un número impar es impar.
- Inicialmente inicialice cnt un contador para almacenar la longitud como 1.
- Iterar entre los elementos de la array, verificar si los elementos consecutivos tienen una suma impar.
- Aumenta el cnt en 1 si tiene una suma impar.
- Si no tiene una suma impar, reinicie cnt en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the Length of the
// longest alternating even odd subarray
#include <bits/stdc++.h>
using namespace std;
// Function to find the longest subarray
int longestEvenOddSubarray(int arr[], int n)
{
// Length of longest
// alternating subarray
int count = 1;
int maxcount = 1;
for (int i = 0; i < n - 1; i++)
{
if (arr[i] % 2 == 0 && arr[i + 1] % 2 != 0)
{
count++;
}
if (arr[i] % 2 != 0 && arr[i + 1] % 2 == 0)
{
count++;
}
if (arr[i] % 2 == 0 && arr[i + 1] % 2 == 0)
{
count = 1;
}
if (arr[i] % 2 != 0 && arr[i + 1] % 2 != 0)
{
count = 1;
}
maxcount = max(maxcount, count);
}
// Length of 'maxcount' can never be 1
// since even odd has to occur in pair or more
// so return 0 if maxcount = 1
if (maxcount == 1)
return 0;
return maxcount;
}
/* Driver code*/
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 7, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << longestEvenOddSubarray(arr, n);
return 0;
}
Java
// Java program to find the Length of the
// longest alternating even odd subarray
import java.util.*;
class GFG{
// Function to find the longest subarray
static int longestEvenOddSubarray(int a[], int n)
{
// Length of longest
// alternating subarray
int longest = 1;
int cnt = 1;
// Iterate in the array
for (int i = 0; i < n - 1; i++)
{
// increment count if consecutive
// elements has an odd sum
if ((a[i] + a[i + 1]) % 2 == 1)
{
cnt++;
}
else
{
// Store maximum count in longest
longest = Math.max(longest, cnt);
// Reinitialize cnt as 1 consecutive
// elements does not have an odd sum
cnt = 1;
}
}
// Length of 'longest' can never be 1
// since even odd has to occur in pair or more
// so return 0 if longest = 1
if (longest == 1)
return 0;
return Math.max(cnt, longest);
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 2, 3, 4, 5, 7, 8 };
int n = a.length;
System.out.println(longestEvenOddSubarray(a, n));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the length of the # longest alternating even odd subarray # Function to find the longest subarray def longestEvenOddSubarray(arr, n): # Length of longest # alternating subarray longest = 1 cnt = 1 # Iterate in the array for i in range(n - 1): # Increment count if consecutive # elements has an odd sum if((arr[i] + arr[i + 1]) % 2 == 1): cnt = cnt + 1 else: # Store maximum count in longest longest = max(longest, cnt) # Reinitialize cnt as 1 consecutive # elements does not have an odd sum cnt = 1 # Length of 'longest' can never be 1 since # even odd has to occur in pair or more # so return 0 if longest = 1 if(longest == 1): return 0 return max(cnt, longest) # Driver Code arr = [ 1, 2, 3, 4, 5, 7, 8 ] n = len(arr) print(longestEvenOddSubarray(arr, n)) # This code is contributed by skylags
C#
// C# program to find the Length of the
// longest alternating even odd subarray
using System;
class GFG{
// Function to find the longest subarray
static int longestEvenOddSubarray(int[] a, int n)
{
// Length of longest
// alternating subarray
int longest = 1;
int cnt = 1;
// Iterate in the array
for(int i = 0; i < n - 1; i++)
{
// Increment count if consecutive
// elements has an odd sum
if ((a[i] + a[i + 1]) % 2 == 1)
{
cnt++;
}
else
{
// Store maximum count in longest
longest = Math.Max(longest, cnt);
// Reinitialize cnt as 1 consecutive
// elements does not have an odd sum
cnt = 1;
}
}
// Length of 'longest' can never be 1
// since even odd has to occur in pair
// or more so return 0 if longest = 1
if (longest == 1)
return 0;
return Math.Max(cnt, longest);
}
// Driver code
static void Main()
{
int[] a = { 1, 2, 3, 4, 5, 7, 8 };
int n = a.Length;
Console.WriteLine(longestEvenOddSubarray(a, n));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript program to find the Length of the
// longest alternating even odd subarray
// Function to find the longest subarray
function longestEvenOddSubarray(a, n)
{
// Length of longest
// alternating subarray
let longest = 1;
let cnt = 1;
// Iterate in the array
for (let i = 0; i < n - 1; i++) {
// increment count if consecutive
// elements has an odd sum
if ((a[i] + a[i + 1]) % 2 == 1)
{
cnt++;
}
else
{
// Store maximum count in longest
longest = Math.max(longest, cnt);
// Reinitialize cnt as 1 consecutive
// elements does not have an odd sum
cnt = 1;
}
}
// Length of 'longest' can never be 1
// since even odd has to occur in pair or more
// so return 0 if longest = 1
if (longest == 1)
return 0;
return Math.max(cnt, longest);
}
/* Driver code*/
let a = [ 1, 2, 3, 4, 5, 7, 8 ];
let n = a.length;
document.write(longestEvenOddSubarray(a, n));
// This code is contributed by Surbhi Tyagi.
</script>
Enfoque 3: simplemente almacenando la naturaleza del elemento anterior que encontramos (par o impar) y comparándolo con el siguiente elemento.
Pasos –
- Almacena la naturaleza del primer elemento en una variable, es decir, si es par o impar. (esta variable almacenará la naturaleza del elemento anterior)
- Ahora itere sobre la array desde el índice 1 hasta n – 1 y siga comprobando si la naturaleza (par/impar) del índice actual no es la misma que la del número anterior.
- Siga almacenando max_length del subarreglo cada vez que la longitud del subarreglo exceda el valor del subarreglo máximo encontrado previamente.
- Devuelve la longitud máxima encontrada del subarreglo.
C++
// C++ code to find longest subarray of alternating even and odds
#include <iostream>
using namespace std;
int maxEvenOdd(int arr[], int n)
{
if (n == 0)
return 0;
int maxLength = 0;
bool prevOdd = arr[0] % 2; // stroring the nature of first element, if remainder = 1, it is odd
int curLength = 1;
for (int i = 1; i < n; i++)
{
if (arr[i] % 2 != prevOdd) // everytime we check if previous element has opposite even/odd nature or not
curLength++;
else
curLength = 1; // reset value when pattern is broken
if (curLength > maxLength) // changing value when new maximum subaaray is found
maxLength = curLength;
prevOdd = arr[i] % 2; // updating even/odd nature of prev number encountered everytime
}
return maxLength;
}
int main()
{
int arr[] = {1,2,3,4,5,3,7,2,9,4}; //longest subarray should be 1 2 3 4 5 , therefore length = 5
int n = sizeof(arr)/sizeof(int);
cout << "Length of longest subarray of even and odds is : " << maxEvenOdd(arr, n);
return 0;
}
//this code is contributed by Anshit Bansal
Producción
Length of longest subarray of even and odds is : 5
Complejidad de tiempo : ya que necesitamos iterar sobre toda la array una vez -> O (n)
Espacio auxiliar : no se usó espacio adicional -> O (1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array