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

Dada una array Arr[] de N enteros. La tarea es encontrar el número mínimo de elementos que se necesitan eliminar de la array para que la suma de los elementos restantes sea impar. Considerando que hay al menos un número impar.
 

Ejemplos: 

Input:  arr[] = {1, 2, 3, 4}
Output: 1
Remove 1 to make array sum odd.

Input: arr[] =  {4, 2, 3, 4}
Output: 0
Sum is already odd.

Enfoque: 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

Como la suma de cualquier número de números pares es par. Así que el recuento de incluso no importa. 
Y la suma de los números impares de un número impar siempre es impar. Entonces, para que la suma de la array sea impar, la cuenta de los números impares debe ser impar. 
Por lo tanto, cuente la cantidad de números impares y verifique si el conteo es impar, entonces no se requieren eliminaciones. De lo contrario, el conteo es par, entonces se debe eliminar 1 número impar.
 

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

// C++ implementation of the above approach
#include <iostream>
using namespace std;
 
// Function to find minimum removals
int findCount(int arr[], int n)
{
    // Count odd numbers
    int countOdd = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] % 2 == 1)
            countOdd++;
 
    // If the counter is odd return 0
    // otherwise return 1
    if (countOdd % 2 == 0)
        return 1;
    else
        return 0;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 5, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << findCount(arr, n);
 
    return 0;
}

// Java implementation of the above approach
class GfG
{
 
// Function to find minimum removals
static int findCount(int arr[], int n)
{
    // Count odd numbers
    int countOdd = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] % 2 == 1)
            countOdd++;
 
    // If the counter is odd return 0
    // otherwise return 1
    if (countOdd % 2 == 0)
        return 1;
    else
        return 0;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 5, 1 };
    int n = arr.length;
 
    System.out.println(findCount(arr, n));
}
}
 
// This code is contributed by
// Prerna Saini

# Python3 implementation of the
# above approach
 
# Function to find minimum removals
def findCount(arr, n) :
     
    # Count odd numbers
    countOdd = 0;
    for i in range(n) :
        if (arr[i] % 2 == 1) :
            countOdd += 1;
 
    # If the counter is odd return 0
    # otherwise return 1
    if (countOdd % 2 == 0) :
        return 1;
    else :
        return 0;
 
# Driver Code
if __name__ == "__main__" :
    arr = [ 1, 2, 3, 5, 1 ];
    n = len(arr) ;
 
    print(findCount(arr, n));
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
 
class GfG
{
 
// Function to find minimum removals
static int findCount(int []arr, int n)
{
    // Count odd numbers
    int countOdd = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] % 2 == 1)
            countOdd++;
 
    // If the counter is odd return 0
    // otherwise return 1
    if (countOdd % 2 == 0)
        return 1;
    else
        return 0;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 5, 1 };
    int n = arr.Length;
 
    Console.WriteLine(findCount(arr, n));
}
}
 
// This code has been contributed by 29AjayKumar

<?php
// PHP implementation of the above approach
 
// Function to find minimum removals
function findCount($arr, $n)
{
    // Count odd numbers
    $countOdd = 0;
    for ($i = 0; $i < $n; $i++)
    if ($arr[$i] % 2 == 1)
        $countOdd++;
 
    // If the counter is odd return 0
    // otherwise return 1
    if ($countOdd % 2 == 0)
        return 1;
    else
        return 0;
}
 
// Driver Code
$arr = array(1, 2, 3, 5, 1);
$n = sizeof($arr);
 
echo(findCount($arr, $n));
 
// This code is contributed by
// Code_Mech.
?>

<script>
 
// Javascript implementation of the above approach
 
// Function to find minimum removals
function findCount(arr, n)
{
    // Count odd numbers
    var countOdd = 0;
    for (var i = 0; i < n; i++)
        if (arr[i] % 2 == 1)
            countOdd++;
 
    // If the counter is odd return 0
    // otherwise return 1
    if (countOdd % 2 == 0)
        return 1;
    else
        return 0;
}
 
// Driver Code
var arr = [ 1, 2, 3, 5, 1 ];
var n = arr.length;
document.write( findCount(arr, n));
 
</script>

1

Complejidad de tiempo : O(n), donde n es el tamaño de la array.

Espacio auxiliar: O(1), no se requiere espacio extra por lo que es una constante.