Volteos mínimos para hacer todos los 1 a la izquierda y los 0 a la derecha | conjunto 2

Dada una array binaria, podemos voltear todos los 1 que están en la parte izquierda y todos los 0 en la parte derecha. Calcule los giros mínimos necesarios para hacer que todos los 1 estén a la izquierda y todos los 0 a la derecha.

Ejemplos: 

Input: 1011000  
Output: 1
1 flip is required to make it 1111000.

Input : 00001 
Output : 2
2 flips required to make it 10000.

Hemos discutido una solución basada en máscara de bits en la publicación a continuación. Volteos mínimos para hacer todos los 1 a la izquierda y los 0 a la derecha | Conjunto 1 (usando máscara de bits)
Se puede hacer con O(N) complejidad de tiempo (donde N es el número de bits) y O(N) memoria adicional 

1. Calcule el número de giros de ‘0’ necesarios mientras se mueve de izquierda a derecha para tener todos los ‘1’ en bits.
2. Calcule el número de vueltas de ‘1’ necesarias mientras se mueve de derecha a izquierda para tener todos los ‘0’ en bits.
3. Atravesar todas las posiciones entre bits y encontrar la suma mínima de ‘0’-flips+’1′-flips de ambas arrays.

Implementación:

// CPP program to find minimum flips required
// to make all 1s in left and 0s in right.
#include <bits/stdc++.h>
using namespace std;
 
int minimalFilps(string bits)
{
    int n = bits.length();
 
    // two arrays will keep the count for number
    // of 0s' and 1s' to be flipped while
    // traversing from left to right and right to
    // left respectively
    int flipsFromLeft[n];
    int flipsFromRight[n];
 
    // Fill flipsFromLeft[]
    int flips = 0;
    for (int i = 0; i < n; i++) {
        if (bits[i] == '0')
            flips++;        
        flipsFromLeft[i] = flips;
    }
 
    // Fill flipsFromRight[]
    flips = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (bits[i] == '1')
            flips++;        
        flipsFromRight[i] = flips;
    }
 
    // initialize minFlip to highest int value. If sum
    // of leftflip and rightFlip is smaller than minflips,
    // then update minFlips
    int minFlips = INT_MAX;
    for (int i = 1; i < n; i++) {
        if (flipsFromLeft[i - 1] + flipsFromRight[i] < minFlips)
            minFlips = flipsFromLeft[i - 1] + flipsFromRight[i];
    }
 
    return minFlips;
}
 
// Driver code
int main()
{
    string bits = "00001";
    cout << minimalFilps(bits) << endl;
    return 0;
}

// Java program to find minimum flips required
// to make all 1s in left and 0s in right.
import java.io.*;
 
class GFG
{
    static int minimalFilps(String bits)
    {
        int n = bits.length();
     
        // two arrays will keep the count
        // for number of 0s' and 1s' to be
        // flipped while traversing from
        // left to right and right to
        // left respectively
        int flipsFromLeft[] = new int[n];
        int flipsFromRight[] =new int[n] ;
     
        // Fill flipsFromLeft[]
        int flips = 0;
        for (int i = 0; i < n; i++)
        {
            if (bits.charAt(i) == '0')
                flips++;        
            flipsFromLeft[i] = flips;
        }
     
        // Fill flipsFromRight[]
        flips = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (bits.charAt(i) == '1')
                flips++;        
            flipsFromRight[i] = flips;
        }
     
        // initialize minFlip to highest int value. If sum
        // of leftflip and rightFlip is smaller than minflips,
        // then update minFlips
        int minFlips = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++)
        {
            if (flipsFromLeft[i - 1] + flipsFromRight[i]
                                              < minFlips)
                minFlips = flipsFromLeft[i - 1]
                           + flipsFromRight[i];
        }
     
        return minFlips;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        String bits = "00001";
        System.out.println(minimalFilps(bits));
         
    }
}
 
// This code is contributed by vt_m.

# Python 3 program to find minimum flips required
# to make all 1s in left and 0s in right.
import sys
 
def minimalFilps(bits):
    n = len(bits)
 
    # two arrays will keep the count for number
    # of 0s' and 1s' to be flipped while
    # traversing from left to right and right to
    # left respectively
    flipsFromLeft = [0 for i in range(n)]
    flipsFromRight = [0 for i in range(n)]
 
    # Fill flipsFromLeft[]
    flips = 0
    for i in range(0, n, 1):
        if (bits[i] == '0'):
            flips = flips + 1   
        flipsFromLeft[i] = flips
     
    # Fill flipsFromRight[]
    flips = 0
    i = n - 1
    while(i >= 0):
        if (bits[i] == '1'):
            flips = flips + 1
        i = i - 1
        flipsFromRight[i] = flips
     
    # initialize minFlip to highest int value.
    # If sum of leftflip and rightFlip is smaller
    # than minflips, then update minFlips
    minFlips = sys.maxsize
    for i in range(1, n, 1):
        if (flipsFromLeft[i - 1] +
            flipsFromRight[i] < minFlips):
            minFlips = (flipsFromLeft[i - 1] +
                        flipsFromRight[i])
     
    return minFlips
 
# Driver code
if __name__ == '__main__':
    bits = "00001"
    print(minimalFilps(bits))
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find minimum flips required
// to make all 1s in left and 0s in right.
using System;
 
class GFG
{
    static int minimalFilps(String bits)
    {
        int n = bits.Length;
     
        // two arrays will keep the count
        // for number of 0s' and 1s' to be
        // flipped while traversing from
        // left to right and right to
        // left respectively
        int []flipsFromLeft = new int[n];
        int []flipsFromRight =new int[n] ;
     
        // Fill flipsFromLeft[]
        int flips = 0;
        for (int i = 0; i < n; i++)
        {
            if (bits[i] == '0')
                flips++;        
            flipsFromLeft[i] = flips;
        }
     
        // Fill flipsFromRight[]
        flips = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (bits[i] == '1')
                flips++;        
            flipsFromRight[i] = flips;
        }
     
        // initialize minFlip to highest int value.
        // If sum of leftflip and rightFlip is smaller
        // than minflips, then update minFlips
        int minFlips = int.MaxValue;
        for (int i = 1; i < n; i++)
        {
            if (flipsFromLeft[i - 1] + flipsFromRight[i] < minFlips)
            minFlips = flipsFromLeft[i - 1] + flipsFromRight[i];
        }
     
        return minFlips;
    }
     
    // Driver code
    public static void Main ()
    {
        string bits = "00001";
        Console.WriteLine(minimalFilps(bits));
         
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find minimum
// flips required to make all
// 1s in left and 0s in right.
 
function minimalFilps($bits)
{
    $n = strlen($bits);
 
    // two arrays will keep the
    // count for number of 0s'
    // and 1s' to be flipped
    // while traversing from
    // left to right and right
    // to left respectively
    $flipsFromLeft[$n] = 0;
    $flipsFromRight[$n] = 0;
 
    // Fill flipsFromLeft[]
    $flips = 0;
    for ($i = 0; $i < $n; $i++) {
        if ($bits[$i] == '0')
            $flips++;        
        $flipsFromLeft[$i] = $flips;
    }
 
    // Fill flipsFromRight[]
    $flips = 0;
    for ($i = $n - 1; $i >= 0; $i--)
    {
        if ($bits[$i] == '1')
            $flips++;        
        $flipsFromRight[$i] = $flips;
    }
 
    // initialize minFlip to
    // highest int value. If sum
    // of leftflip and rightFlip
    // is smaller than minflips,
    // then update minFlips
    $INT_MAX=2147483647;
    $minFlips = $INT_MAX;
    for ($i = 1; $i < $n; $i++)
    {
        if ($flipsFromLeft[$i - 1] +
            $flipsFromRight[$i] < $minFlips)
            $minFlips = $flipsFromLeft[$i - 1] +
                        $flipsFromRight[$i];
    }
 
    return $minFlips;
}
 
    // Driver Code
    $bits = "00001";
    echo minimalFilps($bits) ;
 
// This code is contributed by nitin mittal.
?>

<script>
    // Javascript program to find minimum flips required
    // to make all 1s in left and 0s in right.
     
    function minimalFilps(bits)
    {
        let n = bits.length;
       
        // two arrays will keep the count
        // for number of 0s' and 1s' to be
        // flipped while traversing from
        // left to right and right to
        // left respectively
        let flipsFromLeft = new Array(n);
        flipsFromLeft.fill(0);
        let flipsFromRight =new Array(n);
        flipsFromRight.fill(0);
       
        // Fill flipsFromLeft[]
        let flips = 0;
        for (let i = 0; i < n; i++)
        {
            if (bits[i] == '0')
                flips++;        
            flipsFromLeft[i] = flips;
        }
       
        // Fill flipsFromRight[]
        flips = 0;
        for (let i = n - 1; i >= 0; i--)
        {
            if (bits[i] == '1')
                flips++;        
            flipsFromRight[i] = flips;
        }
       
        // initialize minFlip to highest int value.
        // If sum of leftflip and rightFlip is smaller
        // than minflips, then update minFlips
        let minFlips = Number.MAX_VALUE;
        for (let i = 1; i < n; i++)
        {
            if (flipsFromLeft[i - 1] + flipsFromRight[i] < minFlips)
                minFlips = flipsFromLeft[i - 1] + flipsFromRight[i];
        }
       
        return minFlips;
    }
     
    let bits = "00001";
      document.write(minimalFilps(bits));
  
 // This code is contributed by divyesh072019.
</script>

Producción

 2