Reversiones mínimas de subarreglo requeridas para hacer que un arreglo binario dado se alterne

Dada una array binaria arr[] que consta de un conteo igual de 0 s y 1 s, la tarea es contar el número mínimo de operaciones de inversión de subarreglo necesarias para que la array binaria se alterné. En cada operación invierte cualquier subarreglo del arreglo dado.

Ejemplos:

Entrada: arr[] = { 1, 1, 1, 0, 1, 0, 0, 0 } 
Salida: 2 
Explicación: 
Invertir el subarreglo {arr[1], …, arr[5]} modifica arr[] a { 1, 0, 1, 0, 1, 1, 0, 0 } 
Invertir el subarreglo {arr[5], arr[6]} modifica arr[] a { 1, 0, 1, 0, 1, 0, 1, 0 }, que es alterna. Por lo tanto, la salida requerida es 2.

Entrada: arr[] = { 0, 1, 1, 0 } 
Salida: 1 
Explicación: 
Invertir el subarreglo {arr[2], …, arr[2]} modifica arr[] a { 0, 1, 0, 1 } , que es alterna. Por lo tanto, la salida requerida es 1.

Enfoque: El problema se puede resolver usando la técnica Greedy . La idea es contar los elementos del arreglo que no están presentes en los índices correctos para que el arreglo sea alterno, es decir, contar los elementos iguales consecutivos presentes en el arreglo dado. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos cntOp , para almacenar el recuento mínimo de operaciones de inversión de subarreglo necesarias para que el arreglo dado sea alterno.
• Recorra la array usando la variable i y para cada elemento de la array arr[i] , verifique si es igual a arr[i + 1] o no. Si se encuentra que es cierto, incremente el valor de cntOp .
• Finalmente, imprima el valor de (cntOp + 1) / 2. 
   

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count minimum subarray reversal
// operations required to make array alternating
int minimumcntOperationReq(int arr[], int N)
{
    // Stores minimum count of operations
    // required to make array alternating
    int cntOp = 0;
 
    // Traverse the array
    for (int i = 0; i < N - 1; i++) {
 
        // If arr[i] is greater
        // than arr[i + 1]
        if (arr[i] == arr[i + 1]) {
 
            // Update cntOp
            cntOp++;
        }
    }
 
    return (cntOp + 1) / 2;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 1, 1, 0, 1, 0, 0, 0 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << minimumcntOperationReq(arr, N);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
  
class GFG{
  
// Function to count minimum subarray reversal
// operations required to make array alternating
static int minimumcntOperationReq(int arr[], int N)
{
     
    // Stores minimum count of operations
    // required to make array alternating
    int cntOp = 0;
  
    // Traverse the array
    for(int i = 0; i < N - 1; i++)
    {
         
        // If arr[i] is greater
        // than arr[i + 1]
        if (arr[i] == arr[i + 1])
        {
             
            // Update cntOp
            cntOp++;
        }
    }
    return (cntOp + 1) / 2;
}
  
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 1, 1, 0, 1, 0, 0, 0 };
    int N = arr.length;
  
    System.out.print(minimumcntOperationReq(arr, N));
}
}
 
// This code is contributed by code_hunt

# Python3 program to implement
# the above approach
  
# Function to count minimum subarray
# reversal operations required to make
# array alternating
def minimumcntOperationReq(arr, N):
     
    # Stores minimum count of operations
    # required to make array alternating
    cntOp = 0
  
    # Traverse the array
    for i in range(N - 1):
  
        # If arr[i] is greater
        # than arr[i + 1]
        if (arr[i] == arr[i + 1]):
  
            # Update cntOp
            cntOp += 1
             
    return (cntOp + 1) // 2
 
# Driver Code
arr = [ 1, 1, 1, 0, 1, 0, 0, 0 ]
  
N = len(arr)
  
print(minimumcntOperationReq(arr, N))
 
# This code is contributed by susmitakundugoaldanga

// C# program to implement
// the above approach
using System;
class GFG
{
     
    // Function to count minimum subarray reversal
    // operations required to make array alternating
    static int minimumcntOperationReq(int[] arr, int N)
    {
       
        // Stores minimum count of operations
        // required to make array alternating
        int cntOp = 0;
      
        // Traverse the array
        for (int i = 0; i < N - 1; i++)
        {
      
            // If arr[i] is greater
            // than arr[i + 1]
            if (arr[i] == arr[i + 1])
            {
      
                // Update cntOp
                cntOp++;
            }
        }
      
        return (cntOp + 1) / 2;
    }
   
  // Driver code
  static void Main()
  {
        int[] arr = { 1, 1, 1, 0, 1, 0, 0, 0 };
  
        int N = arr.Length;
      
        Console.WriteLine(minimumcntOperationReq(arr, N));
  }
}
 
// This code is contributed by divyeshrabadiya07

<script>
// javascript program to implement
// the above approach
 
// Function to count minimum subarray reversal
// operations required to make array alternating
function minimumcntOperationReq(arr, N)
{
      
    // Stores minimum count of operations
    // required to make array alternating
    let cntOp = 0;
   
    // Traverse the array
    for(let i = 0; i < N - 1; i++)
    {
          
        // If arr[i] is greater
        // than arr[i + 1]
        if (arr[i] == arr[i + 1])
        {
              
            // Update cntOp
            cntOp++;
        }
    }
    return (cntOp + 1) / 2;
}
 
// Driver code
    let arr = [ 1, 1, 1, 0, 1, 0, 0, 0 ];
    let N = arr.length;
    document.write(Math.floor(minimumcntOperationReq(arr, N)));
     
    // This code is contributed by splevel62.
</script>

2

Complejidad temporal: O(N)  
Espacio auxiliar: O(1)