Dados 2 enteros positivos N y K y un arreglo arr[] , la tarea es encontrar si es posible elegir un subarreglo no vacío del arreglo tal que el subarreglo contenga exactamente K enteros pares.
Ejemplos:
Entrada: N = 4, K = 2, arr[] = {1, 2, 4, 5}
Salida: Sí
Explicación:
Podemos seleccionar el subarreglo {2, 4} que contiene exactamente K = 2 números pares.
Entrada: N = 3, K = 3, arr[] = {2, 4, 5}
Salida: No
Explicación:
Solo hay dos números pares. Por lo tanto, no podemos elegir un subarreglo con K = 3 números pares.
Enfoque: La idea es contar el número de números pares en la array. Ahora puede haber 3 casos:
- Si el recuento de números pares en la array es 0 (es decir, solo hay números impares en la array, entonces no podemos seleccionar ningún subarreglo).
- Si el conteo de números pares en el arreglo es ≥ K , entonces podemos seleccionar fácilmente un subarreglo con exactamente K enteros pares
- De lo contrario, no es posible seleccionar un subarreglo con exactamente K enteros pares
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to check if it is possible to
// choose a subarray that contains exactly
// K even integers
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible to
// choose a subarray that contains exactly
// K even integers
void isPossible(int A[], int n, int k)
{
// Variable to store the count of
// even numbers
int countOfTwo = 0;
for (int i = 0; i < n; i++) {
if (A[i] % 2 == 0) {
countOfTwo++;
}
}
// If we have to select 0 even numbers
// but there is all odd numbers in the array
if (k == 0 && countOfTwo == n)
cout << "NO\n";
// If the count of even numbers is greater than
// or equal to K then we can select a
// subarray with exactly K even integers
else if (countOfTwo >= k) {
cout << "Yes\n";
}
// If the count of even numbers is less than K
// then we cannot select any subarray with
// exactly K even integers
else
cout << "No\n";
}
// Driver code
int main()
{
int arr[] = { 1, 2, 4, 5 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
isPossible(arr, N, K);
return 0;
}
Java
// Java program to check if it is possible to
// choose a subarray that contains exactly
// K even integers
import java.util.*;
class GFG{
// Function to check if it is possible to
// choose a subarray that contains exactly
// K even integers
static void isPossible(int []A, int n, int k)
{
// Variable to store the count of
// even numbers
int countOfTwo = 0;
for (int i = 0; i < n; i++) {
if (A[i] % 2 == 0) {
countOfTwo++;
}
}
// If we have to select 0 even numbers
// but there is all odd numbers in the array
if (k == 0 && countOfTwo == n)
System.out.print("NO");
// If the count of even numbers is greater than
// or equal to K then we can select a
// subarray with exactly K even integers
else if (countOfTwo >= k) {
System.out.print("YES");
}
// If the count of even numbers is less than K
// then we cannot select any subarray with
// exactly K even integers
else
System.out.print("No");
}
// Driver Code
public static void main(String[] args)
{
int []arr = { 1, 2, 4, 5 };
int K = 2;
int n = arr.length;
isPossible(arr, n, K);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program to check if it is possible to
# choose a subarray that contains exactly
# K even integers
# Function to check if it is possible to
# choose a subarray that contains exactly
# K even integers
def isPossible(A, n, k):
# Variable to store the count of
# even numbers
countOfTwo = 0
for i in range(n):
if (A[i] % 2 == 0):
countOfTwo += 1
# If we have to select 0 even numbers
# but there is all odd numbers in the array
if (k == 0 and countOfTwo == n):
print("NO\n")
# If the count of even numbers is greater than
# or equal to K then we can select a
# subarray with exactly K even integers
elif (countOfTwo >= k):
print("Yes\n")
# If the count of even numbers is less than K
# then we cannot select any subarray with
# exactly K even integers
else:
print("No\n")
# Driver code
if __name__ == '__main__':
arr=[1, 2, 4, 5]
K = 2
N = len(arr)
isPossible(arr, N, K)
# This code is contributed by mohit kumar 29
C#
// C# program to check if it is possible to
// choose a subarray that contains exactly
// K even integers
using System;
class GFG{
// Function to check if it is possible to
// choose a subarray that contains exactly
// K even integers
static void isPossible(int []A, int n, int k)
{
// Variable to store the count of
// even numbers
int countOfTwo = 0;
for (int i = 0; i < n; i++) {
if (A[i] % 2 == 0) {
countOfTwo++;
}
}
// If we have to select 0 even numbers
// but there is all odd numbers in the array
if (k == 0 && countOfTwo == n)
Console.Write("NO");
// If the count of even numbers is greater than
// or equal to K then we can select a
// subarray with exactly K even integers
else if (countOfTwo >= k) {
Console.Write("Yes");
}
// If the count of even numbers is less than K
// then we cannot select any subarray with
// exactly K even integers
else
Console.Write("No");
}
// Driver Code
public static void Main()
{
int []arr = { 1, 2, 4, 5 };
int K = 2;
int n = arr.Length;
isPossible(arr, n, K);
}
}
// This code is contributed by AbhiThakur
Javascript
<script>
// JavaScript program to check if it is possible to
// choose a subarray that contains exactly
// K even integers
// Function to check if it is possible to
// choose a subarray that contains exactly
// K even integers
function isPossible(A, n, k)
{
// Variable to store the count of
// even numbers
var countOfTwo = 0;
for (var i = 0; i < n; i++) {
if (A[i] % 2 == 0) {
countOfTwo++;
}
}
// If we have to select 0 even numbers
// but there is all odd numbers in the array
if (k == 0 && countOfTwo == n)
document.write("NO");
// If the count of even numbers is greater than
// or equal to K then we can select a
// subarray with exactly K even integers
else if (countOfTwo >= k) {
document.write("Yes");
}
// If the count of even numbers is less than K
// then we cannot select any subarray with
// exactly K even integers
else
document.write("NO");
}
// Driver code
var arr = [ 1, 2, 4, 5 ];
var K = 2;
var N = arr.length;
isPossible(arr, N, K);
</script>
Producción:
Yes
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)