Inversiones mínimas requeridas para que no haya dos elementos adyacentes iguales

Dada una array binaria arr[] de tamaño N . La tarea es encontrar el número mínimo de inversiones requeridas para que no haya dos elementos adyacentes iguales. Después de una sola inversión, un elemento podría cambiar de 0 a 1 o de 1 a 0 .
Ejemplos: 
 

Entrada: arr[] = {1, 1, 1} 
Salida: 1 
Cambie arr[1] de 1 a 0 y 
la array se convierte en {1, 0, 1}.
Entrada: arr[] = {1, 0, 0, 1, 0, 0, 1, 0} 
Salida: 3 
 

Enfoque: Solo hay dos posibilidades para hacer la array {1, 0, 1, 0, 1, 0, 1, …} o {0, 1, 0, 1, 0, 1, 0, …}. Sean ans_a y ans_b el conteo de cambios requeridos para obtener estas arrays respectivamente. Ahora, la respuesta final será min(ans_a, ans_b) .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// inversions required so that no
// two adjacent elements are same
int min_changes(int a[], int n)
{
    // To store the inversions required
    // to make the array {1, 0, 1, 0, 1, 0, 1, ...}
    // and {0, 1, 0, 1, 0, 1, 0, ...} respectively
    int ans_a = 0, ans_b = 0;
 
    // Find all the changes required
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            if (a[i] == 0)
                ans_a++;
            else
                ans_b++;
        }
        else {
            if (a[i] == 0)
                ans_b++;
            else
                ans_a++;
        }
    }
 
    // Return the required answer
    return min(ans_a, ans_b);
}
 
// Driver code
int main()
{
    int a[] = { 1, 0, 0, 1, 0, 0, 1, 0 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << min_changes(a, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the minimum
// inversions required so that no
// two adjacent elements are same
static int min_changes(int a[], int n)
{
    // To store the inversions required
    // to make the array {1, 0, 1, 0, 1, 0, 1, ...}
    // and {0, 1, 0, 1, 0, 1, 0, ...} respectively
    int ans_a = 0, ans_b = 0;
 
    // Find all the changes required
    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
        {
            if (a[i] == 0)
                ans_a++;
            else
                ans_b++;
        }
        else
        {
            if (a[i] == 0)
                ans_b++;
            else
                ans_a++;
        }
    }
 
    // Return the required answer
    return Math.min(ans_a, ans_b);
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 1, 0, 0, 1, 0, 0, 1, 0 };
    int n = a.length;
 
    System.out.println(min_changes(a, n));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to return the minimum
# inversions required so that no
# two adjacent elements are same
def min_changes(a, n):
 
    # To store the inversions required
    # to make the array {1, 0, 1, 0, 1, 0, 1, ...}
    # and {0, 1, 0, 1, 0, 1, 0, ...} respectively
    ans_a = 0;
    ans_b = 0;
 
    # Find all the changes required
    for i in range(n):
        if (i % 2 == 0):
            if (a[i] == 0):
                ans_a += 1;
            else:
                ans_b += 1;
 
        else:
            if (a[i] == 0):
                ans_b += 1;
            else:
                ans_a += 1;
 
    # Return the required answer
    return min(ans_a, ans_b);
 
# Driver code
if __name__ == '__main__':
 
    a = [ 1, 0, 0, 1, 0, 0, 1, 0 ];
    n = len(a);
 
    print(min_changes(a, n));
 
# This code is contributed by Rajput-Ji

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the minimum
// inversions required so that no
// two adjacent elements are same
static int min_changes(int []a, int n)
{
    // To store the inversions required
    // to make the array {1, 0, 1, 0, 1, 0, 1, ...}
    // and {0, 1, 0, 1, 0, 1, 0, ...} respectively
    int ans_a = 0, ans_b = 0;
 
    // Find all the changes required
    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
        {
            if (a[i] == 0)
                ans_a++;
            else
                ans_b++;
        }
        else
        {
            if (a[i] == 0)
                ans_b++;
            else
                ans_a++;
        }
    }
 
    // Return the required answer
    return Math.Min(ans_a, ans_b);
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 1, 0, 0, 1, 0, 0, 1, 0 };
    int n = a.Length;
 
    Console.WriteLine(min_changes(a, n));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript implementation of the approach
 
// Function to return the minimum
// inversions required so that no
// two adjacent elements are same
function min_changes(a, n) {
    // To store the inversions required
    // to make the array {1, 0, 1, 0, 1, 0, 1, ...}
    // and {0, 1, 0, 1, 0, 1, 0, ...} respectively
    let ans_a = 0, ans_b = 0;
 
    // Find all the changes required
    for (let i = 0; i < n; i++) {
        if (i % 2 == 0) {
            if (a[i] == 0)
                ans_a++;
            else
                ans_b++;
        }
        else {
            if (a[i] == 0)
                ans_b++;
            else
                ans_a++;
        }
    }
 
    // Return the required answer
    return Math.min(ans_a, ans_b);
}
 
// Driver code
let a = [1, 0, 0, 1, 0, 0, 1, 0];
let n = a.length;
 
document.write(min_changes(a, n));
 
</script>

3

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)