Compruebe si la suma de exactamente K elementos del Array puede ser impar o no

Dada una array, arr[] y un entero K . Compruebe si es posible obtener una suma impar eligiendo exactamente K elementos de la array.

Ejemplos: 

Entrada: arr[] = {1, 2, 3}, K = 2 
Salida: Posible 
explicación: 
{2, 3} ⇾ 2 + 3 = 5

Entrada: arr[] = {2, 2, 4, 2}, K = 4 
Salida: No es posible 
Explicación: {2, 2, 4, 2} ⇾ 2 + 2 + 4 + 2 = 10 
No hay otras posibilidades ya que K es igual al tamaño de la array 

Planteamiento: Al observar, se encuentra que hay tres casos.

• Primero, cuenta el número de elementos pares e impares.
• Caso 1: Cuando todos los elementos son pares. Entonces, la suma siempre será par independientemente del valor de K como par + par = par .
• Caso 2: Cuando todos los elementos son impares. Entonces, la suma dependerá solo del valor de K. 
  Si K es impar , entonces la suma será impar ya que cada par impar hace que la suma sea par y, al final, un elemento impar hace que la suma sea impar como par + impar = impar. . 
  Si K es par, entonces todos los elementos impares se emparejan y se vuelven pares, por lo tanto, la suma se vuelve par.
• Caso 3: cuando K <= N, entonces la suma depende solo del número de elementos impares. Si el número de elementos impares es par, entonces la suma será par como impar + impar = par , lo que implica que cada par impar se volverá par. Y si sumamos elementos pares a la suma, la suma seguirá siendo par + par = par .

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

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function returns true if
// it is possible to have
// odd sum
bool isPossible(int arr[],
                int N, int K)
{
    int oddCount = 0, evenCount = 0;
 
    // counting number of odd
    // and even elements
    for (int i = 0; i < N; i++) {
        if (arr[i] % 2 == 0)
            evenCount++;
        else
            oddCount++;
    }
    if (evenCount == N
        || (oddCount == N && K % 2 == 0)
        || (K == N && oddCount % 2 == 0))
        return false;
    else
        return true;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 8 };
    int K = 5;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    if (isPossible(arr, N, K))
        cout << "Possible";
    else
        cout << "Not Possible";
 
    return 0;
}

// Java implementation of the above approach
class GFG{
 
// Function returns true if
// it is possible to have
// odd sum
static boolean isPossible(int arr[],
                          int N, int K)
{
    int oddCount = 0, evenCount = 0;
     
    // Counting number of odd
    // and even elements
    for(int i = 0; i < N; i++)
    {
       if (arr[i] % 2 == 0)
       {
           evenCount++;
       }
       else
       {
           oddCount++;
       }
    }
    if (evenCount == N ||
       (oddCount == N && K % 2 == 0) ||
       (K == N && oddCount % 2 == 0))
    {
        return false;
    }
    else
    {
        return true;
    }
}
     
// Driver code
public static void main (String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5, 8 };
    int K = 5;
    int N = arr.length;
     
    if (isPossible(arr, N, K))
    {
        System.out.println("Possible");
    }
    else
    {
        System.out.println("Not Possible");
    }
}
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the above approach
 
# Function returns true if it
# is possible to have odd sum
def isPossible(arr, N, K):
     
    oddCount = 0
    evenCount = 0
 
    # Counting number of odd
    # and even elements
    for i in range(N):
        if (arr[i] % 2 == 0):
            evenCount += 1
        else:
            oddCount += 1
             
    if (evenCount == N or
       (oddCount == N and K % 2 == 0) or
       (K == N and oddCount % 2 == 0)):
        return False
    else:
        return True
 
# Driver code
if __name__ == '__main__':
     
    arr = [ 1, 2, 3, 4, 5, 8 ]
    K = 5
    N = len(arr)
 
    if (isPossible(arr, N, K)):
        print("Possible")
    else:
        print("Not Possible")
 
# This code is contributed by mohit kumar 29   

// C# implementation of the above approach
using System;
 
class GFG{
 
// Function returns true if
// it is possible to have
// odd sum
static bool isPossible(int []arr,
                       int N, int K)
{
    int oddCount = 0, evenCount = 0;
 
    // Counting number of odd
    // and even elements
    for(int i = 0; i < N; i++)
    {
       if (arr[i] % 2 == 0)
       {
           evenCount++;
       }
       else
       {
           oddCount++;
       }
    }
    if (evenCount == N ||
       (oddCount == N && K % 2 == 0) ||
       (K == N && oddCount % 2 == 0))
    {
        return false;
    }
    else
    {
        return true;
    }
}
 
// Driver code
public static void Main (string[] args)
{
    int []arr = { 1, 2, 3, 4, 5, 8 };
    int K = 5;
    int N = arr.Length;
 
    if (isPossible(arr, N, K))
    {
        Console.WriteLine("Possible");
    }
    else
    {
        Console.WriteLine("Not Possible");
    }
}
}
 
// This code is contributed by AnkitRai01

<script>
// Javascript implementation of the above approach
 
// Function returns true if
// it is possible to have
// odd sum
function isPossible(arr, N, K)
{
    let oddCount = 0, evenCount = 0;
      
    // Counting number of odd
    // and even elements
    for(let i = 0; i < N; i++)
    {
       if (arr[i] % 2 == 0)
       {
           evenCount++;
       }
       else
       {
           oddCount++;
       }
    }
    if (evenCount == N ||
       (oddCount == N && K % 2 == 0) ||
       (K == N && oddCount % 2 == 0))
    {
        return false;
    }
    else
    {
        return true;
    }
}
 
  // Driver Code
     
    let arr = [ 1, 2, 3, 4, 5, 8 ];
    let K = 5;
    let N = arr.length;
      
    if (isPossible(arr, N, K))
    {
        document.write("Possible");
    }
    else
    {
        document.write("Not Possible");
    }
 
// This code is contributed by target_2.
</script>

Possible

Complejidad de tiempo: O(N), donde N representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.