Divida la array en K subarreglos disjuntos de manera que la suma de cada subarreglo sea impar.

Dada una array arr[] que contiene N elementos, la tarea es dividir la array en K(1 ≤ K ≤ N) subarreglos de modo que la suma de los elementos de cada subarreglo sea impar . Imprime el índice inicial (indexación basada en 1) de cada subarreglo después de dividir el arreglo y -1 si no existe tal subarreglo.
Nota: Para todos los subarreglos S ₁ , S ₂ , S ₃ , …, S _K : 
 

• La intersección de S ₁ , S ₂ , S ₃ , …, S _K debe ser NULL.
• La unión de S ₁ , S ₂ , S ₃ , …, S _K debe ser igual a la array.

Ejemplos: 
 

Entrada: N = 5, arr[] = {7, 2, 11, 4, 19}, K = 3 
Salida: 1 3 5 
Explicación: 
Cuando el arreglo dado arr[] se divide en K = 3 partes, los posibles subarreglos son: {7, 2}, {11, 4} y {19} 
Entrada: N = 5, arr[] = {2, 4, 6, 8, 10}, K = 3 
Salida: -1 
Explicación: 
Es imposible dividir la array arr[] en K = 3 subarreglos ya que todos los elementos son pares y la suma de cada subarreglo es par. 
 

Enfoque: Se puede observar fácilmente que para que cualquier subarreglo tenga una suma impar: 
 

1. Dado que solo los valores impares pueden conducir a una suma impar, podemos ignorar los valores pares.
2. El número de valores impares también debe ser impar.
3. Entonces necesitamos al menos K valores impares en la array para K subarreglos. Si K es mayor que el número de elementos impares, la respuesta siempre es -1 .

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

// C++ program to split the array into K
// disjoint subarrays so that the sum of
// each subarray is odd.
  
#include <iostream>
using namespace std;
  
// Function to split the array into K
// disjoint subarrays so that the sum of
// each subarray is odd.
void split(int a[], int n, int k)
{
    // Number of odd elements
    int odd_ele = 0;
  
    // Loop to store the number
    // of odd elements in the array
    for (int i = 0; i < n; i++)
        if (a[i] % 2)
            odd_ele++;
  
    // If the count of odd elements is < K
    // then the answer doesnt exist
    if (odd_ele < k)
        cout << -1;
  
    // If the number of odd elements is
    // greater than K and the extra
    // odd elements are odd, then the
    // answer doesn't exist
    else if (odd_ele > k && (odd_ele - k) % 2)
        cout << -1;
  
    else {
        for (int i = 0; i < n; i++) {
            if (a[i] % 2) {
  
                // Printing the position of
                // odd elements
                cout << i + 1 << " ";
  
                // Decrementing K as we need positions
                // of only first k odd numbers
                k--;
            }
  
            // When the positions of the first K
            // odd numbers are printed
            if (k == 0)
                break;
        }
    }
}
  
// Driver code
int main()
{
    int n = 5;
    int arr[] = { 7, 2, 11, 4, 19 };
    int k = 3;
  
    split(arr, n, k);
}

// Java program to split the array into K
// disjoint subarrays so that the sum of
// each subarray is odd.
class GFG{
   
// Function to split the array into K
// disjoint subarrays so that the sum of
// each subarray is odd.
static void split(int a[], int n, int k)
{
    // Number of odd elements
    int odd_ele = 0;
   
    // Loop to store the number
    // of odd elements in the array
    for (int i = 0; i < n; i++)
        if (a[i] % 2==1)
            odd_ele++;
   
    // If the count of odd elements is < K
    // then the answer doesnt exist
    if (odd_ele < k)
        System.out.print(-1);
   
    // If the number of odd elements is
    // greater than K and the extra
    // odd elements are odd, then the
    // answer doesn't exist
    else if (odd_ele > k && (odd_ele - k) % 2==1)
        System.out.print(-1);
   
    else {
        for (int i = 0; i < n; i++) {
            if (a[i] % 2==1) {
   
                // Printing the position of
                // odd elements
                System.out.print(i + 1+ " ");
   
                // Decrementing K as we need positions
                // of only first k odd numbers
                k--;
            }
   
            // When the positions of the first K
            // odd numbers are printed
            if (k == 0)
                break;
        }
    }
}
   
// Driver code
public static void main(String[] args)
{
    int n = 5;
    int arr[] = { 7, 2, 11, 4, 19 };
    int k = 3;
   
    split(arr, n, k);
}
}
  
// This code is contributed by 29AjayKumar

# Python3 program to split the array into K
# disjoint subarrays so that the sum of
# each subarray is odd.
  
# Function to split the array into K
# disjoint subarrays so that the sum of
# each subarray is odd.
def split(a, n, k) :
  
    # Number of odd elements
    odd_ele = 0;
  
    # Loop to store the number
    # of odd elements in the array
    for i in range(n) :
        if (a[i] % 2) :
            odd_ele += 1;
  
    # If the count of odd elements is < K
    # then the answer doesnt exist
    if (odd_ele < k) :
        print(-1);
  
    # If the number of odd elements is
    # greater than K and the extra
    # odd elements are odd, then the
    # answer doesn't exist
    elif (odd_ele > k and (odd_ele - k) % 2) :
        print(-1);
  
    else :
        for i in range(n) :
            if (a[i] % 2) :
  
                # Printing the position of
                # odd elements
                print(i + 1 ,end= " ");
  
                # Decrementing K as we need positions
                # of only first k odd numbers
                k -= 1;
  
            # When the positions of the first K
            # odd numbers are printed
            if (k == 0) :
                break;
  
# Driver code
if __name__ == "__main__" :
  
    n = 5;
    arr = [ 7, 2, 11, 4, 19 ];
    k = 3;
  
    split(arr, n, k);
      
    # This code is contributed by AnkitRai01

// C# program to split the array into K
// disjoint subarrays so that the sum of
// each subarray is odd.
using System;
  
class GFG{
   
// Function to split the array into K
// disjoint subarrays so that the sum of
// each subarray is odd.
static void split(int []a, int n, int k)
{
    // Number of odd elements
    int odd_ele = 0;
   
    // Loop to store the number
    // of odd elements in the array
    for (int i = 0; i < n; i++)
        if (a[i] % 2 == 1)
            odd_ele++;
   
    // If the count of odd elements is < K
    // then the answer doesnt exist
    if (odd_ele < k)
        Console.Write(-1);
   
    // If the number of odd elements is
    // greater than K and the extra
    // odd elements are odd, then the
    // answer doesn't exist
    else if (odd_ele > k && (odd_ele - k) % 2 == 1)
        Console.Write(-1);
   
    else {
        for (int i = 0; i < n; i++) {
            if (a[i] % 2 == 1) {
   
                // Printing the position of
                // odd elements
                Console.Write(i + 1 + " ");
   
                // Decrementing K as we need positions
                // of only first k odd numbers
                k--;
            }
   
            // When the positions of the first K
            // odd numbers are printed
            if (k == 0)
                break;
        }
    }
}
   
// Driver code
public static void Main(string[] args)
{
    int n = 5;
    int []arr = { 7, 2, 11, 4, 19 };
    int k = 3;
   
    split(arr, n, k);
}
}
  
// This code is contributed by AnkitRai01

<script>
// Javascript program to split the array into K
// disjoint subarrays so that the sum of
// each subarray is odd.
  
  
// Function to split the array into K
// disjoint subarrays so that the sum of
// each subarray is odd.
function split(a, n, k)
{
    // Number of odd elements
    let odd_ele = 0;
  
    // Loop to store the number
    // of odd elements in the array
    for (let i = 0; i < n; i++)
        if (a[i] % 2)
            odd_ele++;
  
    // If the count of odd elements is < K
    // then the answer doesnt exist
    if (odd_ele < k)
        document.write(-1);
  
    // If the number of odd elements is
    // greater than K and the extra
    // odd elements are odd, then the
    // answer doesn't exist
    else if (odd_ele > k && (odd_ele - k) % 2)
        document.write(1);
  
    else {
        for (let i = 0; i < n; i++) {
            if (a[i] % 2) {
  
                // Printing the position of
                // odd elements
                document.write(i + 1 + " ");
  
                // Decrementing K as we need positions
                // of only first k odd numbers
                k--;
            }
  
            // When the positions of the first K
            // odd numbers are printed
            if (k == 0)
                break;
        }
    }
}
  
// Driver code
  
let n = 5;
let arr = [ 7, 2, 11, 4, 19 ];
let k = 3;
  
split(arr, n, k);
  
  
// This code is contributed by gfgking
</script>

1 3 5

Complejidad de tiempo: O(N)
 

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array