Eliminaciones mínimas para hacer que la suma de la array sea uniforme

Dada una array Arr[] de N enteros. Necesitamos escribir un programa para encontrar la cantidad mínima de elementos necesarios para eliminar de la array, de modo que la suma de los elementos restantes sea uniforme. 
Ejemplos: 
 

Input : {1, 2, 3, 4}
Output : 0
Sum is already even

Input : {4, 2, 3, 4}
Output : 1
We need to remove 3 to make
sum even.

La idea para resolver este problema es recordar primero las siguientes propiedades de los IMPAR y los PARES: 
 

• impar + impar = par
• impar + par = impar
• incluso + incluso = incluso
• impar * par = par
• par * par = par
• impar * impar = impar

Entonces, solo necesitamos hacer la suma de los elementos de la array incluso eliminando algunos elementos de la array si es necesario. Podemos notar que la suma de cualquier número de números pares siempre será par. Pero la suma de un número impar de números impares es impar. Es decir, 3 + 3 + 3 = 9 esto es impar pero 3 + 3 + 3 + 3 = 12 que es par. Entonces, solo tendremos que contar la cantidad de elementos impares en la array. Si el conteo de elementos impares en la array es par, entonces no necesitamos eliminar ningún elemento de la array, pero si el conteo de elementos impares en la array es impar, al eliminar cualquiera de los elementos impares de la array, la suma de la array se volverá uniforme. 
A continuación se muestra la implementación de la idea anterior: 
 

// CPP program to find minimum number of
// elements to be removed to make the sum
// even
 
#include <iostream>
using namespace std;
 
int findCount(int arr[], int n)
{
    int count = 0;
 
    for (int i = 0; i < n; i++)
        if (arr[i] % 2 == 1)
            count++; /* counts only odd numbers */
             
    /* if the counter is even return 0
       otherwise return 1 */
    if (count % 2 == 0)
        return 0;
    else
        return 1;
}
 
// Driver Code
int main()
{
    int arr[] = {1, 2, 4, 5, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout <<findCount(arr,n);
 
    return 0;
}

// Java program to find minimum number of
// elements to be removed to make the sum
// even
class GFG {
     
    static int findCount(int arr[], int n)
    {
        int count = 0;
     
        for (int i = 0; i < n; i++)
            if (arr[i] % 2 == 1)
             
                /* counts only odd numbers */
                count++;
                 
        /* if the counter is even return 0
        otherwise return 1 */
        if (count % 2 == 0)
            return 0;
        else
            return 1;
    }
     
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 4, 5, 1};
        int n = arr.length;
         
        System.out.println(findCount(arr, n));
    }
}
 
// This code is contribute by Smitha Dinesh Semwal

# program to find minimum number
# of elements to be removed to
# make the sum even
 
def findCount(arr, n):
 
    count = 0
 
    for i in range(0, n):
        if (arr[i] % 2 == 1):
             
            # counts only odd
            # numbers
            count += -1
             
    # if the counter is
    # even return 0
    # otherwise return 1
    if (count % 2 == 0):
        return 0
    else:
        return 1
 
# Driver Code
arr = [1, 2, 4, 5, 1]
n = len(arr)
 
print(findCount(arr, n))
 
# This code is contributed by
# Smitha Dinesh Semwal

// C# program to find minimum number of
// elements to be removed to make the sum
// even
using System;
 
public class GFG{
     
    static int findCount(int[] arr, int n)
    {
        int count = 0;
     
        for (int i = 0; i < n; i++)
            if (arr[i] % 2 == 1)
             
                /* counts only odd numbers */
                count++;
                 
        /* if the counter is even return 0
        otherwise return 1 */
        if (count % 2 == 0)
            return 0;
        else
            return 1;
    }
     
    // Driver code
    static public void Main ()
    {
        int[] arr = {1, 2, 4, 5, 1};
        int n = arr.Length;
         
        Console.WriteLine(findCount(arr, n));
    }
}
 
// This code is contributed by Ajit.

<?php
// PHP program to find minimum number of
// elements to be removed to make the sum
// even
 
function findCount($arr,$n)
{
    $count = 0;
 
    for ($i = 0; $i < $n; $i++)
        if ($arr[$i] % 2 == 1)
         
            // counts only odd numbers
            $count++;      
             
    /* if the counter is even return
       0 otherwise return 1 */
    if ($count % 2 == 0)
        return 0;
    else
        return 1;
}
 
// Driver Code
$arr = array(1, 2, 4, 5, 1);
$n = 5;
echo findCount($arr,$n);
 
// This code is contributed by
// Manish Shaw (manishshaw1)
?>

<script>
 
// Javascript program to find minimum number of
// elements to be removed to make the sum
// even
function findCount( arr, n)
{
    let count = 0;
 
    for (let i = 0; i < n; i++)
        if (arr[i] % 2 == 1)
            count++; /* counts only odd numbers */
             
    /* if the counter is even return 0
    otherwise return 1 */
    if (count % 2 == 0)
        return 0;
    else
        return 1;
}
 
    // Driver Code
    let arr = [1, 2, 4, 5, 1];
    let n = arr.length;
     
    document.write(findCount(arr,n));
     
// This code is contributed by jana_sayantan.   
     
</script>

Producción: 
 

1

Complejidad de tiempo : O(n), donde n es el número de elementos en la array.