Reversiones mínimas de subarreglo para ordenar un arreglo binario dado

Dada una array binaria A[] de tamaño N , la tarea es encontrar el número mínimo de subarreglos que deben invertirse para ordenar la array binaria.

Ejemplos:

Entrada: N = 4, A[]: {1, 0, 0, 1}          
Salida: 1
Explicación: Invierta la array de 0 a 2 para cambiar la array a {0, 0, 1, 1}

Entrada: N = 4, A[]: {1, 0, 1, 0}
Salida: 2
Explicación: Invierta la array de 1 a 2 y luego de 0 a 3

Planteamiento: La idea para resolver el problema es la siguiente:

Para ordenar A[] itere a través de la array e invierta cada instancia más a la izquierda de un subarreglo de A[] con ‘1’ consecutivos y luego ‘0’ consecutivos.

El recuento de todos estos subarreglos se puede encontrar contando los índices donde A[i] = 1 y el siguiente elemento, es decir, A[i+1] = 0.

Siga los pasos a continuación para implementar la idea:

• Inicialice una variable de conteo con 0.  
• Ejecute un ciclo de 0 a N-2 y en cada iteración haga lo siguiente:
  • Si el i ^-ésimo elemento es 1 y (i+1) el ^ésimo elemento es 0, se incrementa la cuenta en uno ya que existe un subarreglo del tipo [. . .1100. . . ] que debe invertirse para ordenar la array.
• Devuelve la variable de conteo. 

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

// C++ Code to Implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the minimum number of reversals
int minOperations(int n, int A[])
{
    // Declare variable to count the operations
    int count = 0;
 
    for (int i = 0; i < n - 1; i++) {
 
        // Whenever there is a pattern of
        // consecutive 1's followed by 0's
        // It means you have to reverse that
        // subarray, so increase your count by 1
        if (A[i] == 1 && A[i + 1] == 0) {
            count++;
        }
    }
 
    // Return the count
    return count;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 0, 1, 0 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    cout << minOperations(N, A);
    return 0;
}

// Java Code to Implement the approach
public class GFG {
 
  // Function to count the minimum number of reversals
  static int minOperations(int n, int A[])
  {
 
    // Declare variable to count the operations
    int count = 0;
 
    for (int i = 0; i < n - 1; i++) {
 
      // Whenever there is a pattern of
      // consecutive 1's followed by 0's
      // It means you have to reverse that
      // subarray, so increase your count by 1
      if (A[i] == 1 && A[i + 1] == 0) {
        count++;
      }
    }
 
    // Return the count
    return count;
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    int A[] = { 1, 0, 1, 0 };
    int N = A.length;
 
    // Function Call
    System.out.println(minOperations(N, A));
  }
 
}
 
// This code is contributed by AnkThon

# Python3 Code to Implement the approach
 
# Function to count the minimum number of reversals
def minOperations(n, A) :
 
    # Declare variable to count the operations
    count = 0;
 
    for i in range(n-1) :
 
        # Whenever there is a pattern of
        # consecutive 1's followed by 0's
        # It means you have to reverse that
        # subarray, so increase your count by 1
        if (A[i] == 1 and A[i + 1] == 0) :
            count += 1;
 
    # Return the count
    return count;
 
# Driver Code
if __name__ == "__main__" :
 
    A = [ 1, 0, 1, 0 ];
    N = len(A);
 
    # Function Call
    print(minOperations(N, A));
     
    # This code is contributed by AnkThon

// C# Code to Implement the approach
using System;
 
public class GFG {
 
  // Function to count the minimum number of reversals
  static int minOperations(int n, int []A)
  {
 
    // Declare variable to count the operations
    int count = 0;
 
    for (int i = 0; i < n - 1; i++) {
 
      // Whenever there is a pattern of
      // consecutive 1's followed by 0's
      // It means you have to reverse that
      // subarray, so increase your count by 1
      if (A[i] == 1 && A[i + 1] == 0) {
        count++;
      }
    }
 
    // Return the count
    return count;
  }
 
  // Driver Code
  public static void Main (string[] args)
  {
    int []A = { 1, 0, 1, 0 };
    int N = A.Length;
 
    // Function Call
    Console.WriteLine(minOperations(N, A));
  }
 
}
 
// This code is contributed by AnkThon

<script>
    // JavaScript Code to Implement the approach
 
    // Function to count the minimum number of reversals
    const minOperations = (n, A) => {
     
        // Declare variable to count the operations
        let count = 0;
 
        for (let i = 0; i < n - 1; i++) {
 
            // Whenever there is a pattern of
            // consecutive 1's followed by 0's
            // It means you have to reverse that
            // subarray, so increase your count by 1
            if (A[i] == 1 && A[i + 1] == 0) {
                count++;
            }
        }
 
        // Return the count
        return count;
    }
 
    // Driver Code
    let A = [1, 0, 1, 0];
    let N = A.length
 
    // Function Call
    document.write(minOperations(N, A));
 
// This code is contributed by rakeshsahni
 
</script>

2

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