Compruebe si K elementos de array distintos forman una suma impar

Dada una array A[] de tamaño N , la tarea es verificar si es posible obtener una suma impar usando K elementos distintos de la array.
Ejemplos: 

Entrada: N = 4, K = 2, A = {10, 19, 14, 14} 
Salida: SÍ 
Explicación: 
19 + 14 = 33, que es impar
Entrada: N = 3, K = 3, A = {101, 102, 103} 
Salida: NO 
Explicación: 
101 + 102 + 103 = 306, que es par 

Acercarse: 

• Veamos algunas propiedades matemáticas básicas:

EVEN + EVEN = EVEN
ODD  + ODD  = EVEN
EVEN + ODD  = ODD

• De las propiedades anteriores, podemos concluir que cuando se suma un número impar de enteros impares a cualquier número de enteros pares, el resultado siempre será impar. 
   

Ejemplos: 

• 3 + 2 + 6 = 11 (impar)
• 1 + 3 + 7 + 4 = 15 (impar)

Por lo tanto, siga los pasos a continuación para resolver el problema: 

• Cuente distintos elementos pares e impares presentes en la array.
• Si K o más elementos impares están presentes en la array, imprima «Sí».
• De lo contrario, para cada conteo impar de números impares, verifique si hay suficientes números pares en la array o no.
• Si ocurre alguno de estos casos, escriba «Sí». De lo contrario, escriba “No”.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return if
// odd sum is possible or not
bool oddSum(vector<int>& A,
            int N, int K)
{
 
    // Stores distinct odd elements
    set<int> Odd;
    // Stores distinct even elements
    set<int> Even;
 
    // Iterating through given array
    for (int i = 0; i < N; i++) {
 
        // If element is even
        if (A[i] % 2 == 0) {
            Even.insert(A[i]);
        }
        // If element is odd
        else {
            Odd.insert(A[i]);
        }
    }
 
    // If atleast K elements
    // in the array are odd
    if (Odd.size() >= K)
        return true;
 
    bool flag = false;
 
    // Check for all odd frequencies
    // of odd elements whether
    // sufficient even numbers
    // are present or not
    for (int i = 1; i < K; i += 2) {
 
        // Count of even numbers
        // required
        int needed = K - i;
 
        // If required even numbers
        // are present in the array
        if (needed <= Even.size()) {
 
            return true;
        }
    }
 
    return flag;
}
 
// Driver Program
int main()
{
    int K = 5;
    vector<int> A = { 12, 1, 7, 7, 26, 18 };
    int N = 3;
 
    if (oddSum(A, N, K))
        cout << "YES";
    else
        cout << "NO";
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to return if
// odd sum is possible or not
static boolean oddSum(int []A,
                      int N, int K)
{
     
    // Stores distinct odd elements
    HashSet<Integer> Odd = new HashSet<Integer>();
     
    // Stores distinct even elements
    HashSet<Integer> Even = new HashSet<Integer>();
 
    // Iterating through given array
    for(int i = 0; i < N; i++)
    {
         
        // If element is even
        if (A[i] % 2 == 0)
        {
            Even.add(A[i]);
        }
             
        // If element is odd
        else
        {
            Odd.add(A[i]);
        }
    }
 
    // If atleast K elements
    // in the array are odd
    if (Odd.size() >= K)
        return true;
 
    boolean flag = false;
 
    // Check for all odd frequencies
    // of odd elements whether
    // sufficient even numbers
    // are present or not
    for(int i = 1; i < K; i += 2)
    {
         
        // Count of even numbers
        // required
        int needed = K - i;
             
        // If required even numbers
        // are present in the array
        if (needed <= Even.size())
        {
            return true;
        }
    }
    return flag;
}
 
// Driver code
public static void main(String[] args)
{
    int K = 5;
    int []A = { 12, 1, 7, 7, 26, 18 };
    int N = 3;
 
    if (oddSum(A, N, K))
        System.out.print("YES");
    else
        System.out.print("NO");
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program for
# the above approach
 
# Function to return if
# odd sum is possible or not
def oddSum(A, N, K):
 
    # Stores distinct odd elements
    Odd = set([])
    # Stores distinct even elements
    Even = set([])
  
    # Iterating through given array
    for i in range (N):
  
        # If element is even
        if (A[i] % 2 == 0):
            Even.add(A[i])
        
        # If element is odd
        else:
            Odd.add(A[i])
  
    # If atleast K elements
    # in the array are odd
    if (len(Odd) >= K):
        return True
  
    flag = False
  
    # Check for all odd frequencies
    # of odd elements whether
    # sufficient even numbers
    # are present or not
    for i in range (1, K, 2):
  
        # Count of even numbers
        # required
        needed = K - i
  
        # If required even numbers
        # are present in the array
        if (needed <= len(Even)):
            return True
  
    return flag
  
# Driver Program
if __name__ == "__main__":
 
    K = 5
    A = [12, 1, 7,
         7, 26, 18]
    N = 3
  
    if (oddSum(A, N, K)):
        print ("YES")
    else:
        print("NO")
  
# This code is contributed by Chitranayal

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to return if
// odd sum is possible or not
static bool oddSum(int []A, int N, int K)
{
     
    // Stores distinct odd elements
    HashSet<int> Odd = new HashSet<int>();
     
    // Stores distinct even elements
    HashSet<int> Even = new HashSet<int>();
 
    // Iterating through given array
    for(int i = 0; i < N; i++)
    {
         
        // If element is even
        if (A[i] % 2 == 0) 
        {
            Even.Add(A[i]);
        }
         
        // If element is odd
        else
        {
            Odd.Add(A[i]);
        }
    }
     
    // If atleast K elements
    // in the array are odd
    if (Odd.Count >= K)
        return true;
 
    bool flag = false;
 
    // Check for all odd frequencies
    // of odd elements whether
    // sufficient even numbers
    // are present or not
    for(int i = 1; i < K; i += 2)
    {
         
        // Count of even numbers
        // required
        int needed = K - i;
             
        // If required even numbers
        // are present in the array
        if (needed <= Even.Count)
        {
            return true;
        }
    }
    return flag;
}
 
// Driver code
public static void Main(String[] args)
{
    int K = 5;
    int []A = { 12, 1, 7, 7, 26, 18 };
    int N = 3;
 
    if (oddSum(A, N, K))
        Console.Write("YES");
    else
        Console.Write("NO");
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript program for the above approach
 
    // Function to return if
   // odd sum is possible or not
    function oddSum(A,N,K)
    {
        // Stores distinct odd elements
    let Odd = new Set();
      
    // Stores distinct even elements
    let Even = new Set();
  
    // Iterating through given array
    for(let i = 0; i < N; i++)
    {
          
        // If element is even
        if (A[i] % 2 == 0)
        {
            Even.add(A[i]);
        }
              
        // If element is odd
        else
        {
            Odd.add(A[i]);
        }
    }
  
    // If atleast K elements
    // in the array are odd
    if (Odd.size >= K)
        return true;
  
    let flag = false;
  
    // Check for all odd frequencies
    // of odd elements whether
    // sufficient even numbers
    // are present or not
    for(let i = 1; i < K; i += 2)
    {
          
        // Count of even numbers
        // required
        let needed = K - i;
              
        // If required even numbers
        // are present in the array
        if (needed <= Even.size)
        {
            return true;
        }
    }
    return flag;
    }
     
    // Driver code
    let K = 5;
    let A=[12, 1, 7, 7, 26, 18];
    let N = 3;
    if (oddSum(A, N, K))
        document.write("YES");
    else
        document.write("NO");
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

NO

Complejidad del tiempo: O(N)