El mínimo cambia para particionar una array binaria para que tenga primero 0 y luego 1

Dada una array de n enteros que contienen solo 0 y 1. Encuentre los cambios mínimos (cambiar de 0 a 1 o viceversa) necesarios para que la array se particione, es decir, tenga primero 0 que 1. Debe haber al menos un 0 al principio y puede haber cero o más 1 al final. 

Input: arr[] = {1, 0, 1, 1, 0}
Output: 2
Toggle the first and last element i.e.,
1 -> 0
0 -> 1
Final array will become:
arr[] = {0 0 1 1 1}
Since first two consecutive elements are all 0s
and rest three consecutive elements are all 1s.
Therefore minimum two toggles are required.

Input: arr[] = {0, 1, 0, 0, 1, 1, 1}
Output: 1

Input: arr[] = {1, 1}
Output: 1
There should be at least one 0.

Input: arr[] = {0, 0}
Output: 0
There can zero 1s. 

Si observamos la pregunta, encontraremos que definitivamente existirá un punto de 0 a n-1 donde todos los elementos que quedan hasta ese punto deben contener todos los 0 y el derecho al punto debe contener todos los 1. Aquellos índices que no obedezcan esta ley deberán ser eliminados. La idea es contar todos los 0 de izquierda a derecha.  

Let zero[i] denotes the number of 0's till ith
index, then for each i, minimum number of
toggles required can be written as: i - zero[i]
 + zero[n] - zero[i] . The part i - zero[i]
indicates number of 1's to be toggled and the 
part zero[n] - zero[i] indicates number of 0's
to be toggled.

After that we just need to take minimum of 
all to get the final answer. 

Implementación:

// C++ program to find minimum toggle required
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate minimum toggling
// required by using Dynamic programming
int minToggle(int arr[], int n)
{
    int zero[n + 1];
    zero[0] = 0;
 
    // Fill entries in zero[] such that zero[i]
    // stores count of zeroes to the left of i
    // (exl
    for (int i = 1; i <= n; ++i) {
        // If zero found update zero[] array
        if (arr[i - 1] == 0)
            zero[i] = zero[i - 1] + 1;
        else
            zero[i] = zero[i - 1];
    }
 
    // Finding the minimum toggle required from
    // every index(0 to n-1)
    int ans = n;
    for (int i = 1; i <= n; ++i)
        ans = min(ans, i - zero[i] + zero[n] - zero[i]);
 
    return ans;
}
 
// Driver Program
int main()
{
    int arr[] = { 1, 0, 1, 1, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minToggle(arr, n) << "\n";
    return 0;
}

// Java program to find minimum
// toggle required
import java.io.*;
 
class GFG {
 
    // Function to calculate minimum toggling
    // required by using Dynamic programming
    static int minToggle(int arr[], int n)
    {
        int zero[] = new int[n + 1];
        zero[0] = 0;
 
        // Fill entries in zero[] such that
        // zero[i] stores count of zeroes
        // to the left of i (exl
        for (int i = 1; i <= n; ++i) {
            // If zero found update zero[] array
            if (arr[i - 1] == 0)
                zero[i] = zero[i - 1] + 1;
            else
                zero[i] = zero[i - 1];
        }
 
        // Finding the minimum toggle required
        // from every index(0 to n-1)
        int ans = n;
        for (int i = 1; i <= n; ++i)
            ans = Math.min(ans, i - zero[i] + zero[n]
                                    - zero[i]);
 
        return ans;
    }
 
    // Driver Program
    public static void main(String[] args)
    {
        int arr[] = { 1, 0, 1, 1, 0 };
        int n = arr.length;
        System.out.println(minToggle(arr, n));
    }
}
 
// This code is contributed by vt_m.

# Python program to find
# minimum toggle required
 
# Function to calculate
# minimum toggling
# required by using
# Dynamic programming
def minToggle(arr, n):
 
    zero =[0 for i in range(n + 1+1)]
    zero[0] = 0
  
    # Fill entries in zero[]
    # such that zero[i]
    # stores count of zeroes
    # to the left of i
    # (exl
    for i in range(1, n + 1):
     
        # If zero found
        # update zero[] array
        if (arr[i-1] == 0):
            zero[i] = zero[i-1] + 1
        else:
            zero[i] = zero[i-1]
  
    # Finding the minimum
    # toggle required from
    # every index(0 to n-1)
    ans = n
    for i in range(1, n + 1):
        ans = min(ans, i - zero[i] + zero[n] - zero[i])
  
    return ans
     
# Driver Program
 
arr = [1, 0, 1, 1, 0]
n = len(arr)
 
print(minToggle(arr, n))
 
# This code is contributed
# by Anant Agarwal.

// C# program to find minimum
// toggle required
using System;
 
class GFG {
 
    // Function to calculate minimum toggling
    // required by using Dynamic programming
    static int minToggle(int[] arr, int n)
    {
         
        int[] zero = new int[n + 1];
        zero[0] = 0;
 
        // Fill entries in zero[] such that
        // zero[i] stores count of zeroes
        // to the left of i (exl
        for (int i = 1; i <= n; ++i) {
             
            // If zero found update zero[]
            // array
            if (arr[i - 1] == 0)
                zero[i] = zero[i - 1] + 1;
            else
                zero[i] = zero[i - 1];
        }
 
        // Finding the minimum toggle required
        // from every index(0 to n-1)
        int ans = n;
         
        for (int i = 1; i <= n; ++i)
            ans = Math.Min(ans, i - zero[i] +
                            zero[n] - zero[i]);
 
        return ans;
    }
 
    // Driver Program
    public static void Main()
    {
        int[] arr = { 1, 0, 1, 1, 0 };
        int n = arr.Length;
         
        Console.WriteLine(minToggle(arr, n));
    }
}
 
// This code is contributed by Sam007.

<?php
// php program to find minimum toggle required
 
// Function to calculate minimum toggling
// required by using Dynamic programming
function minToggle($arr, $n)
{
    $zero[0] = 0;
    $zero[$n + 1]=0;
 
 
    // Fill entries in zero[] such that zero[i]
    // stores count of zeroes to the left of i
    // (exl
    for ($i = 1; $i <= $n; ++$i) {
         
        // If zero found update zero[] array
        if ($arr[$i - 1] == 0)
            $zero[$i] = $zero[$i - 1] + 1;
        else
            $zero[$i] = $zero[$i - 1];
    }
 
    // Finding the minimum toggle required from
    // every index(0 to n-1)
    $ans = $n;
     
    for ($i = 1; $i <= $n; ++$i)
        $ans = min($ans, $i - $zero[$i]
                      + $zero[$n] - $zero[$i]);
 
    return $ans;
}
 
// Driver Program
    $arr = array( 1, 0, 1, 1, 0 );
    $n = sizeof($arr);
     
    echo minToggle($arr, $n) , "\n";
 
// This code is contributed by nitin mittal.
?>

<script>
    // Javascript program to find minimum
    // toggle required
     
    // Function to calculate minimum toggling
    // required by using Dynamic programming
    function minToggle(arr, n)
    {
           
        let zero = new Array(n + 1);
        zero[0] = 0;
   
        // Fill entries in zero[] such that
        // zero[i] stores count of zeroes
        // to the left of i (exl
        for (let i = 1; i <= n; ++i) {
               
            // If zero found update zero[]
            // array
            if (arr[i - 1] == 0)
                zero[i] = zero[i - 1] + 1;
            else
                zero[i] = zero[i - 1];
        }
   
        // Finding the minimum toggle required
        // from every index(0 to n-1)
        let ans = n;
           
        for (let i = 1; i <= n; ++i)
            ans = Math.min(ans, i - zero[i] + zero[n] - zero[i]);
   
        return ans;
    }
     
    let arr = [ 1, 0, 1, 1, 0 ];
    let n = arr.length;
 
    document.write(minToggle(arr, n));
     
</script>

2

Complejidad temporal: O(n) 
Espacio auxiliar: O(n)

Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.