Encuentre las operaciones mínimas necesarias para hacer una array hermosa

Dada una array binaria (considérela como cíclica con inicio y final unidos) de longitud N que tiene solo uno y cero donde  . La tarea es encontrar la operación mínima necesaria para hacer que la array sea hermosa. 
Se dice que una array es hermosa si no tiene ceros ni unos consecutivos. Si no es posible, imprima -1.
En una operación, puede hacer lo siguiente: 
 

1. Cortar la array en dos partes.
2. Invierta una de estas dos partes.
3. Une los extremos correspondientes de estas dos partes, creando una array completa nuevamente.

Encuentre el número mínimo de operaciones anteriores que se realizarán en la array para que sea hermosa, de modo que no contenga ningún uno o cero consecutivo.
Ejemplos : 
 

Input : A[] = { 1, 1, 0, 0 }
Output : 1
Explanation: 
Make first cut between A[0] and A[1]
and second cut between A[2] and A[3].
Reverse array A[1] to A[2] and tie both array together.
Thus new array is A = [1, 0, 1, 0] which is beautiful.

Input : A[] = { 1, 1, 0, 0, 0 }
Output : -1

Enfoque: el objetivo es hacer que la array tenga la forma A1[] = { 1, 0, 1, …, 0, 1, 0 } o A2[] = { 0, 1, 0, … 1, 0, 1 }. 
 

• Si tenemos un número impar de elementos, entonces es imposible hacer que la array sea hermosa, ya que siempre tenemos un número binario más que otro. Por lo tanto, devolvemos -1.
• Si tenemos un número par de elementos, entonces podemos hacer cualquiera de los arreglos A1 o A2 solo cuando tenemos ceros binarios y unos iguales.
• Además, el corte mínimo requerido es la cantidad de ceros o unos consecutivos que tenemos y serán iguales.
• Entonces, iteramos la array y mantenemos el conteo de ceros y unos y también ceros consecutivos.
• Si cero = uno, devuelve el recuento de ceros consecutivos, de lo contrario, devuelve -1.

Nota : un caso especial es cuando solo hay un elemento en la array. Si solo hay 1 elemento presente en la array, entonces la array ya es hermosa, por lo que la respuesta es cero.
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP implementation of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum operations
// required to make array beautiful
int minOperations(int A[], int n)
{
    if (n & 1)
        return -1;
 
    int zeros = 0, consZeros = 0, ones = 0;
 
    for (int i = 0; i < n; ++i) {
        A[i] == 0 ? zeros++ : ones++;
 
        // counting consecutive zeros.
        if (i + 1 < n) {
            if (A[i] == 0 && A[i + 1] == 0)
                consZeros++;
        }
    }
 
    // check that start and end are same
    if (A[0] == A[n - 1] && A[0] == 0)
        consZeros++;
 
    // check is zero and one are equal
    if (zeros == ones)
        return consZeros;
    else
        return -1;
}
 
// Driver program
int main()
{
    int A[] = { 1, 1, 0, 0 };
    int n = sizeof(A) / sizeof(A[0]);
 
    cout << minOperations(A, n);
 
    return 0;
}

// Java implementation of above approach
 
class GFG{
// Function to find minimum operations
// required to make array beautiful
static int minOperations(int[] A, int n)
{
    if ((n & 1)>0)
        return -1;
 
    int zeros = 0, consZeros = 0, ones = 0;
 
    for (int i = 0; i < n; ++i) {
        if(A[i] == 0) zeros++; else  ones++;
 
        // counting consecutive zeros.
        if (i + 1 < n) {
            if (A[i] == 0 && A[i + 1] == 0)
                consZeros++;
        }
    }
 
    // check that start and end are same
    if (A[0] == A[n - 1] && A[0] == 0)
        consZeros++;
 
    // check is zero and one are equal
    if (zeros == ones)
        return consZeros;
    else
        return -1;
}
 
// Driver program
public static void main(String[] args)
{
    int[] A =new int[] { 1, 1, 0, 0 };
    int n = A.length;
 
    System.out.println(minOperations(A, n));
 
}
}
// This code is contributed by mits

# Python 3 implementation of
# above approach
 
# Function to find minimum operations
# required to make array beautiful
def minOperations(A, n) :
 
    if n & 1 :
        return -1
 
    zeros, consZeros, ones = 0, 0, 0
 
    for i in range(n) :
 
        if A[i] :
            zeros += 1
        else :
            ones += 1
 
        # counting consecutive zeros.
        if( i + 1 < n) :
 
            if A[i] == 0 and A[i + 1] == 0 :
                consZeros += 1
 
    # check that start and end are same
    if A[0] == A[n - 1] and A[0] == 0 :
        consZeros += 1
 
    # check is zero and one are equal
    if zeros == ones :
        return consZeros
    else :
        return -1
 
# Driver code
if __name__ == "__main__" :
 
    A = [1, 1, 0, 0]
    n = len(A)
 
    print(minOperations(A, n))
     
# This code is contributed by ANKITRAI1

// C# implementation of above approach
 
class GFG{
// Function to find minimum operations
// required to make array beautiful
static int minOperations(int[] A, int n)
{
    if ((n & 1)>0)
        return -1;
 
    int zeros = 0, consZeros = 0, ones = 0;
 
    for (int i = 0; i < n; ++i) {
        if(A[i] == 0) zeros++; else ones++;
 
        // counting consecutive zeros.
        if (i + 1 < n) {
            if (A[i] == 0 && A[i + 1] == 0)
                consZeros++;
        }
    }
 
    // check that start and end are same
    if (A[0] == A[n - 1] && A[0] == 0)
        consZeros++;
 
    // check is zero and one are equal
    if (zeros == ones)
        return consZeros;
    else
        return -1;
}
 
// Driver program
static void Main()
{
    int[] A =new int[] { 1, 1, 0, 0 };
    int n = A.Length;
 
    System.Console.WriteLine(minOperations(A, n));
 
}
}
// This code is contributed by mits

<?php
// PHP implementation of above approach
 
// Function to find minimum operations
// required to make array beautiful
function minOperations($A, $n)
{
    if ($n & 1)
        return -1;
 
    $zeros = 0;
    $consZeros = 0;
    $ones = 0;
 
    for ($i = 0; $i < $n; ++$i)
    {
        $A[$i] == 0 ? $zeros++ : $ones++;
 
        // counting consecutive zeros.
        if (($i + 1) < $n)
        {
            if ($A[$i] == 0 &&
                $A[$i + 1] == 0)
                $consZeros++;
        }
    }
 
    // check that start and
    // end are same
    if ($A[0] == $A[$n - 1] &&
        $A[0] == 0)
        $consZeros++;
 
    // check is zero and one are equal
    if ($zeros == $ones)
        return $consZeros;
    else
        return -1;
}
 
// Driver Code
$A = array( 1, 1, 0, 0 );
$n = sizeof($A);
 
echo minOperations($A, $n);
 
// This code is contributed
// by akt_mit
?>

<script>
    // Javascript implementation of above approach
     
    // Function to find minimum operations
    // required to make array beautiful
    function minOperations(A, n)
    {
        if ((n & 1)>0)
            return -1;
 
        let zeros = 0, consZeros = 0, ones = 0;
 
        for (let i = 0; i < n; ++i) {
            if(A[i] == 0) zeros++; else ones++;
 
            // counting consecutive zeros.
            if (i + 1 < n) {
                if (A[i] == 0 && A[i + 1] == 0)
                    consZeros++;
            }
        }
 
        // check that start and end are same
        if (A[0] == A[n - 1] && A[0] == 0)
            consZeros++;
 
        // check is zero and one are equal
        if (zeros == ones)
            return consZeros;
        else
            return -1;
    }
     
    let A = [ 1, 1, 0, 0 ];
    let n = A.length;
   
    document.write(minOperations(A, n));
         
</script>

1

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)