Compruebe si es posible dividir el Array dado en K subconjuntos de suma impar

Dada una array arr[] de longitud N , la tarea es verificar si es posible dividir la array dada en K subconjuntos no vacíos y que no se intersecan, de modo que la suma de los elementos de cada subconjunto sea impar.
Ejemplos: 
 

Entrada: K = 4, arr[] = {1, 3, 4, 7, 5, 3, 1} 
Salida: Sí 
Explicación: 
[1], [3, 4, 7, 5], [3] y [1 ] son ​​los posibles subconjuntos.
Entrada: K = 3, arr[] = {2, 3, 4, 7, 2} 
Salida: No 
Explicación: 
La array dada no se puede dividir en 3 subconjuntos con suma impar. 
 

Planteamiento: 
Para resolver el problema mencionado anteriormente necesitamos observar los siguientes puntos: 
 

• Los números pares no cambian la paridad de la suma de los subconjuntos, por lo que podemos ignorarlos.
• Si el número de enteros impares en la array es menor que K , entonces no podemos dividirlo en K subconjuntos con sumas impares ya que no hay suficientes enteros impares.
• Sea cnt el número de enteros impares . Entonces, la respuesta siempre será posible solo si cnt % 2 = K % 2 . Esto se debe a que distribuiremos un número impar en los primeros K-1 subconjuntos y cnt – K – 1 números impares en el último subconjunto . Ahora, dado que cnt y K tienen la misma paridad, cnt – K – 1 será impar y la suma también es impar.

Por lo tanto, para resolver el problema, cuente el número de enteros impares presentes en la array. Que esto sea cnt . La respuesta será ‘Sí’ si cnt es mayor que K y cnt % 2 = K % 2 . De lo contrario, no es posible una respuesta e imprimimos ‘No’.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation to check if it is
// possible to split array into K
// subsets with odd sum
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if array
// can be split in required K
// subsets
bool checkArray(int n, int k, int arr[])
{
    // Store count of
    // odd numbers
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        // Check if element
        // is odd
        if (arr[i] & 1)
            cnt += 1;
    }
 
    // Check if split is possible
    if (cnt >= k && cnt % 2 == k % 2)
        return true;
    else
        return false;
}
 
// Driver Program
int main()
{
    int arr[] = { 1, 3, 4, 7, 5, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int k = 4;
 
    if (checkArray(n, k, arr))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation to check if it
// is possible to split array into K
// subsets with odd sum
 
class GFG{
     
// Function to check if array
// can be split in required K
// subsets
static boolean checkArray(int n, int k,
                          int arr[])
{
     
    // Store count of odd numbers
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
         
       // Check if element is odd
       if ((arr[i] & 1) != 0)
           cnt += 1;
    }
     
    // Check if split is possible
    if (cnt >= k && cnt % 2 == k % 2)
        return true;
    else
        return false;
}
 
// Driver code
public static void main (String []args)
{
    int arr[] = { 1, 3, 4, 7, 5, 3, 1 };
    int n = arr.length;
    int k = 4;
 
    if (checkArray(n, k, arr))
        System.out.print("Yes");
    else
        System.out.print("No");
}
}
 
// This code is contributed by chitranayal

# Python3 implementation to check if
# it is possible to split array into
# K subsets with odd sum
 
# Function to check if array
# can be split in required K
# subsets
def checkArray(n, k, arr):
     
    # Store count of
    # odd numbers
    cnt = 0
    for i in range(n):
         
        # Check if element
        # is odd
        if (arr[i] & 1):
            cnt += 1
 
    # Check if split is possible
    if (cnt >= k and cnt % 2 == k % 2):
        return True
    else:
        return False
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 3, 4, 7, 5, 3, 1 ]
    n = len(arr)
    k = 4
 
    if (checkArray(n, k, arr)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

// C# implementation to check if it
// is possible to split array into K
// subsets with odd sum
using System;
class GFG{
 
// Function to check if array
// can be split in required K
// subsets
static bool checkArray(int n, int k,
                       int []arr)
{
     
    // Store count of odd numbers
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
         
        // Check if element is odd
        if ((arr[i] & 1) != 0)
            cnt += 1;
    }
     
    // Check if split is possible
    if (cnt >= k && cnt % 2 == k % 2)
        return true;
    else
        return false;
}
 
// Driver code
public static void Main (string []args)
{
    int []arr = { 1, 3, 4, 7, 5, 3, 1 };
    int n = arr.Length;
    int k = 4;
 
    if (checkArray(n, k, arr))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by AnkitRai01

<script>
// javascript implementation to check if it
// is possible to split array into K
// subsets with odd sum
    // Function to check if array
    // can be split in required K
    // subsets
    function checkArray(n , k , arr) {
 
        // Store count of odd numbers
        var cnt = 0;
        for (i = 0; i < n; i++) {
 
            // Check if element is odd
            if ((arr[i] & 1) != 0)
                cnt += 1;
        }
 
        // Check if split is possible
        if (cnt >= k && cnt % 2 == k % 2)
            return true;
        else
            return false;
    }
 
    // Driver code
     
        var arr = [ 1, 3, 4, 7, 5, 3, 1 ];
        var n = arr.length;
        var k = 4;
 
        if (checkArray(n, k, arr))
            document.write("Yes");
        else
            document.write("No");
 
// This code contributed by gauravrajput1
</script>

Yes

Complejidad de tiempo: O(N)