Python | Número de elementos que se eliminarán de modo que el producto de los elementos adyacentes sea siempre par

Dada una array de N enteros. La tarea es eliminar el número de elementos tal que en la array resultante el producto de dos valores adyacentes cualquiera sea par.

Ejemplos: 

Input  : arr[] = {1, 2, 3}
Output : 0

Input  : arr[] = {1, 3, 5, 4, 2}
Output : 2
Remove 1 and 3.

Planteamiento: El producto de 2 números es par si alguno de ellos es par. Esto significa que por cada par de números consecutivos, si ambos son impares, elimine uno de ellos. 
Entonces, para hacer que el producto de los elementos adyacentes sea par, todos los elementos deben ser pares o elementos alternativos pares-impares. Así que el siguiente algoritmo codicioso funciona: 

• Revisa todos los elementos en orden.
• Si todos los elementos son pares, se devuelve «0».
• Si todos los elementos son impares, se devuelve «n».
• De lo contrario, cuente el número de pares impares consecutivos.
• Devuelve el recuento mínimo.

A continuación se muestra la implementación de Python: 
 

# Python 3 implementation of the 
# above approach
   
# Function to find minimum number of 
# eliminations such that product of all 
# adjacent elements is even
def min_elimination(n, arr):
    countOdd = 0
    counteven = 0
    # Stores the new value
    for i in range(n):
           
        # Count odd and even  numbers
        if (arr[i] % 2):
            countOdd += 1
        else:
            counteven+= 1
    # if all are even
    if counteven == n:
        return 0
 
    # if all are odd
    if countOdd == n:
        return n
    else:
        countpair = 0
        for i in range(1, n):
            if (arr[i] % 2 == 1 and arr[i-1] % 2 == 1):
                countpair+= 1
        return countpair
   
# Driver code
if __name__ == '__main__':
    arr = [1, 2, 3, 7, 9]
    n = len(arr)
   
    print(min_elimination(n, arr))

Producción: 

2

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)