Dado un arreglo arr[] de N enteros positivos y un entero K , la tarea es encontrar la longitud mínima del subarreglo tal que existan al menos K pares de elementos pares e impares siempre que el elemento par ocurra antes que el elemento impar. Si no existe tal subarreglo, imprima “-1” .
Ejemplos:
Entrada: K = 2, A[] = {1, 2, 3, 4, 5}
Salida : 4
Explicación:
El subarreglo {2, 3, 4, 5} tiene una longitud de 4, que es el mínimo. Tiene al menos K(= 2) pares como {2, 3}, {2, 5} y {4, 5}.Entrada: K = 3, A[] = {2, 3, 4, 1, 2, 3}
Salida: 4
Explicación: El subarreglo {2, 3, 4, 1} tiene una longitud de 4, que es el mínimo. Tiene al menos K(= 3) pares como {2, 3}, {2, 1} y {4, 1}.
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subarreglos posibles del arreglo dado y encontrar el conteo de pares que satisfacen los criterios dados en cada subarreglo. Después de verificar todos los subarreglos, imprima la longitud mínima de ese subarreglo que tenga al menos K pares de elementos pares e impares, de modo que el elemento par ocurra antes que el elemento impar.
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el problema dado se puede resolver utilizando la técnica de dos punteros . Considere una array A[] de tamaño N entonces,
- Considere dos punteros p1 y p2, inicialice p1 como 0 y p2 como -1 , estos dos punteros representarán el tamaño de ventana actual.
- Vamos, hay dos variables num_pairs (almacena el número de pares válidos) y final_ans (almacena la longitud del subarreglo mínimo posible con al menos K pares válidos y se inicializa con INT_MAX ).
- Siga los pasos a continuación hasta que p2 esté fuera de rango, es decir, hasta que p2<N :
- Fije p1 en la misma posición y siga aumentando p2 y siga agregando los nuevos pares válidos generados mientras aumenta p2. Continúe con este proceso, hasta que el número de pares válidos sea menor que K. Una vez que num_pairs sea al menos K , actualice final_ans y deténgase.
- Ahora, comience a aumentar p1 y fije p2 en la misma posición (donde estaba después del paso anterior). Mientras aumenta p1, siga restando los pares válidos que fueron el resultado de la inclusión del elemento A[p1] y luego incremente p1. Este proceso continúa hasta que el recuento de pares válidos sea mayor o igual a K . Mientras realiza este proceso, realice un seguimiento del subarreglo de longitud mínima (fin_ans) a medida que p1 y p2 cambian.
- Devuelve final_ans .
Contando el número de pares válidos en el rango {p1, p2}:
- Mantener una array de conteo acumulativo pares[N] e impares[N] para el número de elementos pares e impares hasta el índice i, A[0, i]
- Ahora, cada vez que se aumenta el puntero p2, sumamos el número de pares válidos generados al incluir el elemento A[p2] en num_pairs. Hay dos casos:
Caso 1: cuando A[p2] es par , al considerar este elemento en el subarreglo existente (A[p1, p2-1]), no habrá ningún aumento en el número de pares válidos.
Caso 2: Cuando A[p2] es impar , al considerar este elemento en el subarreglo existente (A[p1, p2-1]), se generará el número de pares válidos que son iguales al número de números pares dentro del rango {p1, p2-1}. Dado que cada número par en ese rango forma un nuevo par con este elemento impar recién agregado, esto se puede calcular directamente usando la array evens[N] .
- Ahora, mientras aumenta el puntero p1, reste el número de pares válidos de num_pairs que fueron generados por la inclusión del elemento A[p1] .
Hay dos casos:
Caso 1: cuando A[p1] es impar , al eliminar este elemento del subarreglo existente (A[p1, p2]), no habrá ninguna disminución en el número de pares válidos.
Caso 2: cuando A[p1] es par , al eliminar este elemento del subarreglo existente (A[p1, p2]), se debe eliminar la cantidad de pares válidos que es igual a la cantidad de números impares dentro del rango { p1+1, p2}. Dado que cada número impar en el rango A{p+1, p2} habría formado un par con el número par A[p1], esto se puede calcular directamente usando la array odds[N] .
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the length of the
// smallest possible sub array with at least K
// valid pairs.
int CalculateMinimumSubarray(int A[], int N, int K)
{
// Vector to store the cumulative count of the number
// of even numbers and odd numbers.
// For every i, evens[i] and odds[i] represents
// the number of evens and odd elements
// encountered till index 'i'
vector<int> evens(N, 0), odds(N, 0);
if (A[0] % 2 == 0)
evens[0] = 1;
else
odds[0] = 1;
// Calculating the cumulative even and
// odd vectors
for (int i = 1; i < N; i++) {
evens[i] += evens[i - 1] + (A[i] % 2 == 0);
odds[i] += odds[i - 1] + (A[i] % 2 == 1);
}
// Store the minimum length subarray with
// atleast K valid pairs
int final_ans = INT_MAX;
// Initializing two pointers.
int p1 = 0, p2 = -1;
// Stores the number of valid pairs in
// the range {p1, p2}
int num_pairs = 0;
// Incrementing p2
while (p2 < N) {
// Incrementing pointer p2 until there
// are atleast K valid pairs
// between the range {p1, p2}.
while (p2 < N && num_pairs < K) {
p2++;
// If p2 >= N, stop.
if (p2 >= N) {
break;
}
// If A[p2] is an even number, then
// the number of valid pairs won't
// increase, so just continue.
if (A[p2] % 2 == 0) {
continue;
}
// If A[p2] is an odd number, then those many
// number of valid pairs will be generated which
// which are equal to the number of even numbers
// within the range {p1, p2-1}. Since every even
// number forms a new pair with this odd element.
int no_evens;
if (p1 == 0) {
no_evens = evens[p2];
}
else {
no_evens = evens[p2] - evens[p1 - 1];
}
// Increment the num_pairs variable with
// the number of even numbers in the range
// {p1, p2-1} as calculated above.
num_pairs = num_pairs + no_evens;
// Update final_ans
if (num_pairs >= K) {
final_ans = min(final_ans, p2 - p1 + 1);
}
}
if (p2 >= N) {
break;
}
// Increment the pointer p1 until
// num_pairs >= K.
while (num_pairs >= K && p1 < p2) {
// Update final_ans
if (num_pairs >= K) {
final_ans = min(final_ans, p2 - p1 + 1);
}
// If A[p1] is an odd number, then removing that
// element won't decrease the num_pairs.
if (A[p1] % 2 != 0) {
p1++;
continue;
}
// If A[p1] is an even number, then we should
// subtract those number of valid pairs from
// num_pairs which is equal to the number of odd
// numbers in the range {p1+1, p2}. Since every
// odd number in the range {p1+1, p2} would have
// formed a pair with the even number at A[p1]
int no_odds;
if (p1 == 0) {
no_odds = odds[p2];
}
else {
no_odds = odds[p2] - odds[p1 - 1];
}
// now we decrease the num_pairs with the value
// calculated above, that is number of odd
// numbers from A[p1+1, p2]
num_pairs = num_pairs - no_odds;
p1++;
}
}
// If final_ans is updated atleast once,
// then it means there is atleast one sub-array
// of some size with atleast K valid pairs.
// And however we have calculated the subarray
// of minimum length.
// So we return its length.
if (final_ans != INT_MAX) {
return final_ans;
}
// If the final_ans is never updated,
// it means that there is no subarray
// of any size with atleast K valid
// pairs. So we return -1.
return -1;
}
// Driver Code
int main()
{
int N = 5;
int K = 2;
int A[5] = { 1, 2, 3, 4, 5 };
cout << CalculateMinimumSubarray(A, N, K) << endl;
}
Java
import java.util.Arrays;
class GFG {
// Function to calculate the length of the
// smallest possible sub array with at least K
// valid pairs.
public static int CalculateMinimumSubarray(int A[], int N, int K)
{
// Vector to store the cumulative count of the number
// of even numbers and odd numbers.
// For every i, evens[i] and odds[i] represents
// the number of evens and odd elements
// encountered till index 'i'
int[] evens = new int[N];
int[] odds = new int[N];
Arrays.fill(evens, 0);
Arrays.fill(odds, 0);
if (A[0] % 2 == 0)
evens[0] = 1;
else
odds[0] = 1;
// Calculating the cumulative even and
// odd vectors
for (int i = 1; i < N; i++) {
evens[i] += evens[i - 1] + ((A[i] % 2 == 0) ? 1 : 0);
odds[i] += odds[i - 1] + ((A[i] % 2 == 1) ? 1 : 0);
}
// Store the minimum length subarray with
// atleast K valid pairs
int final_ans = Integer.MAX_VALUE;
// Initializing two pointers.
int p1 = 0, p2 = -1;
// Stores the number of valid pairs in
// the range {p1, p2}
int num_pairs = 0;
// Incrementing p2
while (p2 < N) {
// Incrementing pointer p2 until there
// are atleast K valid pairs
// between the range {p1, p2}.
while (p2 < N && num_pairs < K) {
p2++;
// If p2 >= N, stop.
if (p2 >= N) {
break;
}
// If A[p2] is an even number, then
// the number of valid pairs won't
// increase, so just continue.
if (A[p2] % 2 == 0) {
continue;
}
// If A[p2] is an odd number, then those many
// number of valid pairs will be generated which
// which are equal to the number of even numbers
// within the range {p1, p2-1}. Since every even
// number forms a new pair with this odd element.
int no_evens;
if (p1 == 0) {
no_evens = evens[p2];
} else {
no_evens = evens[p2] - evens[p1 - 1];
}
// Increment the num_pairs variable with
// the number of even numbers in the range
// {p1, p2-1} as calculated above.
num_pairs = num_pairs + no_evens;
// Update final_ans
if (num_pairs >= K) {
final_ans = Math.min(final_ans, p2 - p1 + 1);
}
}
if (p2 >= N) {
break;
}
// Increment the pointer p1 until
// num_pairs >= K.
while (num_pairs >= K && p1 < p2) {
// Update final_ans
if (num_pairs >= K) {
final_ans = Integer.min(final_ans, p2 - p1 + 1);
}
// If A[p1] is an odd number, then removing that
// element won't decrease the num_pairs.
if (A[p1] % 2 != 0) {
p1++;
continue;
}
// If A[p1] is an even number, then we should
// subtract those number of valid pairs from
// num_pairs which is equal to the number of odd
// numbers in the range {p1+1, p2}. Since every
// odd number in the range {p1+1, p2} would have
// formed a pair with the even number at A[p1]
int no_odds;
if (p1 == 0) {
no_odds = odds[p2];
} else {
no_odds = odds[p2] - odds[p1 - 1];
}
// now we decrease the num_pairs with the value
// calculated above, that is number of odd
// numbers from A[p1+1, p2]
num_pairs = num_pairs - no_odds;
p1++;
}
}
// If final_ans is updated atleast once,
// then it means there is atleast one sub-array
// of some size with atleast K valid pairs.
// And however we have calculated the subarray
// of minimum length.
// So we return its length.
if (final_ans != Integer.MAX_VALUE) {
return final_ans;
}
// If the final_ans is never updated,
// it means that there is no subarray
// of any size with atleast K valid
// pairs. So we return -1.
return -1;
}
// Driver Code
public static void main(String args[]) {
int N = 5;
int K = 2;
int A[] = { 1, 2, 3, 4, 5 };
System.out.println(CalculateMinimumSubarray(A, N, K));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
import sys
# Function to calculate the length of the
# smallest possible sub array with at least K
# valid pairs.
def CalculateMinimumSubarray(A, N, K):
# Vector to store the cumulative count of the number
# of even numbers and odd numbers.
# For every i, evens[i] and odds[i] represents
# the number of evens and odd elements
# encountered till index 'i'
evens = [0 for i in range(N)]
odds = [0 for i in range(N)]
if (A[0] % 2 == 0):
evens[0] = 1
else:
odds[0] = 1
# Calculating the cumulative even and
# odd vectors
for i in range(1,N,1):
evens[i] += evens[i - 1] + (A[i] % 2 == 0)
odds[i] += odds[i - 1] + (A[i] % 2 == 1)
# Store the minimum length subarray with
# atleast K valid pairs
final_ans = sys.maxsize
# Initializing two pointers.
p1 = 0
p2 = -1
# Stores the number of valid pairs in
# the range {p1, p2}
num_pairs = 0
# Incrementing p2
while (p2 < N):
# Incrementing pointer p2 until there
# are atleast K valid pairs
# between the range {p1, p2}.
while (p2 < N and num_pairs < K):
p2 += 1
# If p2 >= N, stop.
if (p2 >= N):
break
# If A[p2] is an even number, then
# the number of valid pairs won't
# increase, so just continue.
if (A[p2] % 2 == 0):
continue
# If A[p2] is an odd number, then those many
# number of valid pairs will be generated which
# which are equal to the number of even numbers
# within the range {p1, p2-1}. Since every even
# number forms a new pair with this odd element.
no_evens = 0
if (p1 == 0):
no_evens = evens[p2]
else:
no_evens = evens[p2] - evens[p1 - 1]
# Increment the num_pairs variable with
# the number of even numbers in the range
# {p1, p2-1} as calculated above.
num_pairs = num_pairs + no_evens
# Update final_ans
if (num_pairs >= K):
final_ans = min(final_ans, p2 - p1 + 1)
if (p2 >= N):
break
# Increment the pointer p1 until
# num_pairs >= K.
while (num_pairs >= K and p1 < p2):
# Update final_ans
if (num_pairs >= K):
final_ans = min(final_ans, p2 - p1 + 1)
# If A[p1] is an odd number, then removing that
# element won't decrease the num_pairs.
if (A[p1] % 2 != 0):
p1 += 1
continue
# If A[p1] is an even number, then we should
# subtract those number of valid pairs from
# num_pairs which is equal to the number of odd
# numbers in the range {p1+1, p2}. Since every
# odd number in the range {p1+1, p2} would have
# formed a pair with the even number at A[p1]
no_odds = 0
if (p1 == 0):
no_odds = odds[p2]
else:
no_odds = odds[p2] - odds[p1 - 1]
# now we decrease the num_pairs with the value
# calculated above, that is number of odd
# numbers from A[p1+1, p2]
num_pairs = num_pairs - no_odds
p1 += 1
# If final_ans is updated atleast once,
# then it means there is atleast one sub-array
# of some size with atleast K valid pairs.
# And however we have calculated the subarray
# of minimum length.
# So we return its length.
if (final_ans != sys.maxsize):
return final_ans
# If the final_ans is never updated,
# it means that there is no subarray
# of any size with atleast K valid
# pairs. So we return -1.
return -1
# Driver Code
if __name__ == '__main__':
N = 5
K = 2
A = [1, 2, 3, 4, 5]
print(CalculateMinimumSubarray(A, N, K))
# This code is contributed by SURENDRA_GANGWAR.
C#
using System;
public class GFG{
// Function to calculate the length of the
// smallest possible sub array with at least K
// valid pairs.
public static int CalculateMinimumSubarray(int[] A, int N, int K)
{
// Vector to store the cumulative count of the number
// of even numbers and odd numbers.
// For every i, evens[i] and odds[i] represents
// the number of evens and odd elements
// encountered till index 'i'
int[] evens = new int[N];
int[] odds = new int[N];
Array.Fill(evens, 0);
Array.Fill(odds, 0);
if (A[0] % 2 == 0)
evens[0] = 1;
else
odds[0] = 1;
// Calculating the cumulative even and
// odd vectors
for (int i = 1; i < N; i++) {
evens[i] += evens[i - 1] + ((A[i] % 2 == 0) ? 1 : 0);
odds[i] += odds[i - 1] + ((A[i] % 2 == 1) ? 1 : 0);
}
// Store the minimum length subarray with
// atleast K valid pairs
int final_ans = Int32.MaxValue;
// Initializing two pointers.
int p1 = 0, p2 = -1;
// Stores the number of valid pairs in
// the range {p1, p2}
int num_pairs = 0;
// Incrementing p2
while (p2 < N) {
// Incrementing pointer p2 until there
// are atleast K valid pairs
// between the range {p1, p2}.
while (p2 < N && num_pairs < K) {
p2++;
// If p2 >= N, stop.
if (p2 >= N) {
break;
}
// If A[p2] is an even number, then
// the number of valid pairs won't
// increase, so just continue.
if (A[p2] % 2 == 0) {
continue;
}
// If A[p2] is an odd number, then those many
// number of valid pairs will be generated which
// which are equal to the number of even numbers
// within the range {p1, p2-1}. Since every even
// number forms a new pair with this odd element.
int no_evens;
if (p1 == 0) {
no_evens = evens[p2];
} else {
no_evens = evens[p2] - evens[p1 - 1];
}
// Increment the num_pairs variable with
// the number of even numbers in the range
// {p1, p2-1} as calculated above.
num_pairs = num_pairs + no_evens;
// Update final_ans
if (num_pairs >= K) {
final_ans = Math.Min(final_ans, p2 - p1 + 1);
}
}
if (p2 >= N) {
break;
}
// Increment the pointer p1 until
// num_pairs >= K.
while (num_pairs >= K && p1 < p2) {
// Update final_ans
if (num_pairs >= K) {
final_ans = Math.Min(final_ans, p2 - p1 + 1);
}
// If A[p1] is an odd number, then removing that
// element won't decrease the num_pairs.
if (A[p1] % 2 != 0) {
p1++;
continue;
}
// If A[p1] is an even number, then we should
// subtract those number of valid pairs from
// num_pairs which is equal to the number of odd
// numbers in the range {p1+1, p2}. Since every
// odd number in the range {p1+1, p2} would have
// formed a pair with the even number at A[p1]
int no_odds;
if (p1 == 0) {
no_odds = odds[p2];
} else {
no_odds = odds[p2] - odds[p1 - 1];
}
// now we decrease the num_pairs with the value
// calculated above, that is number of odd
// numbers from A[p1+1, p2]
num_pairs = num_pairs - no_odds;
p1++;
}
}
// If final_ans is updated atleast once,
// then it means there is atleast one sub-array
// of some size with atleast K valid pairs.
// And however we have calculated the subarray
// of minimum length.
// So we return its length.
if (final_ans != Int32.MaxValue) {
return final_ans;
}
// If the final_ans is never updated,
// it means that there is no subarray
// of any size with atleast K valid
// pairs. So we return -1.
return -1;
}
// Driver Code
static public void Main (){
int N = 5;
int K = 2;
int[] A = { 1, 2, 3, 4, 5 };
Console.WriteLine(CalculateMinimumSubarray(A, N, K));
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to calculate the length of the
// smallest possible sub array with at least K
// valid pairs.
function CalculateMinimumSubarray(A, N, K)
{
// Vector to store the cumulative count of the number
// of even numbers and odd numbers.
// For every i, evens[i] and odds[i] represents
// the number of evens and odd elements
// encountered till index 'i'
let evens = new Array(N).fill(0);
let odds = new Array(N).fill(0)
if (A[0] % 2 == 0)
evens[0] = 1;
else
odds[0] = 1;
// Calculating the cumulative even and
// odd vectors
for (let i = 1; i < N; i++) {
evens[i] += evens[i - 1] + (A[i] % 2 == 0);
odds[i] += odds[i - 1] + (A[i] % 2 == 1);
}
// Store the minimum length subarray with
// atleast K valid pairs
let final_ans = Number.MAX_VALUE;
// Initializing two pointers.
let p1 = 0, p2 = -1;
// Stores the number of valid pairs in
// the range {p1, p2}
let num_pairs = 0;
// Incrementing p2
while (p2 < N) {
// Incrementing pointer p2 until there
// are atleast K valid pairs
// between the range {p1, p2}.
while (p2 < N && num_pairs < K) {
p2++;
// If p2 >= N, stop.
if (p2 >= N) {
break;
}
// If A[p2] is an even number, then
// the number of valid pairs won't
// increase, so just continue.
if (A[p2] % 2 == 0) {
continue;
}
// If A[p2] is an odd number, then those many
// number of valid pairs will be generated which
// which are equal to the number of even numbers
// within the range {p1, p2-1}. Since every even
// number forms a new pair with this odd element.
let no_evens;
if (p1 == 0) {
no_evens = evens[p2];
}
else {
no_evens = evens[p2] - evens[p1 - 1];
}
// Increment the num_pairs variable with
// the number of even numbers in the range
// {p1, p2-1} as calculated above.
num_pairs = num_pairs + no_evens;
// Update final_ans
if (num_pairs >= K) {
final_ans = Math.min(final_ans, p2 - p1 + 1);
}
}
if (p2 >= N) {
break;
}
// Increment the pointer p1 until
// num_pairs >= K.
while (num_pairs >= K && p1 < p2) {
// Update final_ans
if (num_pairs >= K) {
final_ans = Math.min(final_ans, p2 - p1 + 1);
}
// If A[p1] is an odd number, then removing that
// element won't decrease the num_pairs.
if (A[p1] % 2 != 0) {
p1++;
continue;
}
// If A[p1] is an even number, then we should
// subtract those number of valid pairs from
// num_pairs which is equal to the number of odd
// numbers in the range {p1+1, p2}. Since every
// odd number in the range {p1+1, p2} would have
// formed a pair with the even number at A[p1]
let no_odds;
if (p1 == 0) {
no_odds = odds[p2];
}
else {
no_odds = odds[p2] - odds[p1 - 1];
}
// now we decrease the num_pairs with the value
// calculated above, that is number of odd
// numbers from A[p1+1, p2]
num_pairs = num_pairs - no_odds;
p1++;
}
}
// If final_ans is updated atleast once,
// then it means there is atleast one sub-array
// of some size with atleast K valid pairs.
// And however we have calculated the subarray
// of minimum length.
// So we return its length.
if (final_ans != Number.MAX_VALUE) {
return final_ans;
}
// If the final_ans is never updated,
// it means that there is no subarray
// of any size with atleast K valid
// pairs. So we return -1.
return -1;
}
// Driver Code
let N = 5;
let K = 2;
let A = [1, 2, 3, 4, 5];
document.write(CalculateMinimumSubarray(A, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción
4
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por jaisaikuntala1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA