Haga que todos los elementos de la array sean iguales con las operaciones dadas

Dada una array arr[] de enteros positivos, encuentre el número mínimo de operaciones requeridas para hacer que todos los elementos de la array sean iguales donde:  

1. Si hay un número impar, incremente el elemento y el siguiente elemento adyacente en 1.
2. Cada incremento cuesta una operación.

Nota: si hay algún número en arr[] que es impar después de todas las operaciones, imprima -1.

Ejemplos: 

Entrada: arr[] = {2, 3, 4, 5, 6} 
Salida: 4 
Explicación: 
Sume 1 a 3 (en el 1er índice) y agregue 1 a su elemento adyacente 4 (2do índice). 
Ahora la array se convierte en {2, 4, 5, 5, 6}. 
Agregue 1 a 5 (en el segundo índice) y agregue 1 a su elemento adyacente 5 (3er índice). 
Ahora la array se convierte en {2, 4, 6, 6, 6}. 
La array resultante tiene todos los números pares. 
El número total de operaciones para 4 incrementos es 4.

Entrada: arr[] = {5, 6} 
Salida: -1 
Explicación: 
sumando 1 a 5 (índice 0), luego tenemos que incrementar 1 a su elemento adyacente 6 (índice 1). 
Ahora la array se convierte en {6, 7}. 
Y nos queda 1 número impar después de todos los incrementos posibles. Por lo tanto, no podemos hacer que todos los elementos de la array sean iguales.  

Enfoque: 
este problema se puede resolver utilizando el enfoque codicioso . Los siguientes son los pasos: 

1. Recorre la array dada arr[] .
2. Si ocurre un elemento impar, entonces incremente ese elemento en 1 para hacerlo par y el siguiente elemento adyacente en 1.
3. Repita el paso anterior para todos los elementos impares de la array dada arr[] .
4. Si todos los elementos en arr[] son ​​pares, imprima el número de operaciones.
5. De lo contrario, imprima -1.

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

// C++ program to make all array
// element even
#include "bits/stdc++.h"
using namespace std;
 
// Function to count the total
// number of operations needed to make
// all array element even
int countOperations(int arr[], int n)
{
    int count = 0;
 
    // Traverse the given array
    for (int i = 0; i < n - 1; i++) {
 
        // If an odd element occurs
        // then increment that element
        // and next adjacent element
        // by 1
        if (arr[i] & 1) {
            arr[i]++;
            arr[i + 1]++;
            count += 2;
        }
    }
 
    // Traverse the array if any odd
    // element occurs then return -1
    for (int i = 0; i < n; i++) {
        if (arr[i] & 1)
            return -1;
    }
 
    // Returns the count of operations
    return count;
}
 
int main()
{
    int arr[] = { 2, 3, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(int);
    cout << countOperations(arr, n);
    return 0;
}

// Java program to make all array
// element even
class GFG
{
 
// Function to count the total
// number of operations needed to make
// all array element even
static int countOperations(int arr[], int n)
{
    int count = 0;
 
    // Traverse the given array
    for (int i = 0; i < n - 1; i++)
    {
 
        // If an odd element occurs
        // then increment that element
        // and next adjacent element
        // by 1
        if (arr[i] % 2 == 1)
        {
            arr[i]++;
            arr[i + 1]++;
            count += 2;
        }
    }
 
    // Traverse the array if any odd
    // element occurs then return -1
    for (int i = 0; i < n; i++)
    {
        if (arr[i] % 2 == 1)
            return -1;
    }
 
    // Returns the count of operations
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 2, 3, 4, 5, 6 };
    int n = arr.length;
    System.out.print(countOperations(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to make all array
# element even
 
# Function to count the total
# number of operations needed to make
# all array element even
def countOperations(arr, n) :
 
    count = 0;
 
    # Traverse the given array
    for i in range(n - 1) :
 
        # If an odd element occurs
        # then increment that element
        # and next adjacent element
        # by 1
        if (arr[i] & 1) :
            arr[i] += 1;
            arr[i + 1] += 1;
            count += 2;
 
    # Traverse the array if any odd
    # element occurs then return -1
    for i in range(n) :
        if (arr[i] & 1) :
            return -1;
 
    # Returns the count of operations
    return count;
 
if __name__ == "__main__" :
 
    arr = [ 2, 3, 4, 5, 6 ];
    n = len(arr);
    print(countOperations(arr, n));
     
    # This code is contributed by AnkitRai01

// C# program to make all array
// element even
using System;
 
class GFG
{
 
// Function to count the total
// number of operations needed to make
// all array element even
static int countOperations(int []arr, int n)
{
    int count = 0;
 
    // Traverse the given array
    for (int i = 0; i < n - 1; i++)
    {
 
        // If an odd element occurs
        // then increment that element
        // and next adjacent element
        // by 1
        if (arr[i] % 2 == 1)
        {
            arr[i]++;
            arr[i + 1]++;
            count += 2;
        }
    }
 
    // Traverse the array if any odd
    // element occurs then return -1
    for (int i = 0; i < n; i++)
    {
        if (arr[i] % 2 == 1)
            return -1;
    }
 
    // Returns the count of operations
    return count;
}
 
// Driver code
public static void Main()
{
    int []arr = { 2, 3, 4, 5, 6 };
    int n = arr.Length;
    Console.Write(countOperations(arr, n));
}
}
 
// This code is contributed by AnkitRai01

<script>
// Javascript program to make all array
// element even
 
// Function to count the total
// number of operations needed to make
// all array element even
function countOperations(arr, n)
{
    let count = 0;
 
    // Traverse the given array
    for (let i = 0; i < n - 1; i++) {
 
        // If an odd element occurs
        // then increment that element
        // and next adjacent element
        // by 1
        if (arr[i] & 1) {
            arr[i]++;
            arr[i + 1]++;
            count += 2;
        }
    }
 
    // Traverse the array if any odd
    // element occurs then return -1
    for (let i = 0; i < n; i++) {
        if (arr[i] & 1)
            return -1;
    }
 
    // Returns the count of operations
    return count;
}
 
 
let arr = [ 2, 3, 4, 5, 6 ];
let n = arr.length;
document.write(countOperations(arr, n));
 
// This code is contributed by _saurabh_jaiswal
</script>

4

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