Cambios mínimos requeridos para formar una string binaria dada donde cada cambio también cambia todos los bits a su derecha

Dada una string S , la tarea es encontrar los giros mínimos necesarios para convertir una string binaria inicial que consta de solo ceros en S, donde cada giro de un carácter también voltea todos los caracteres posteriores. 
Ejemplos: 
 

Entrada: S = “01011” 
Salida: 3 
Explicación: 
String inicial – “00000” 
Voltear el segundo bit – “01111” 
Voltear el 3er bit – “01000” 
Voltear el 4to bit – “01011” 
Total de volteos = 3
Entrada: S = “01001” 
Salida: 3 
Explicación: 
String inicial – “00000” 
Voltear el segundo bit – “01111” 
Voltear el 3er bit – “01000” 
Voltear el 5to bit – “01001” 
Total Flips = 3 
 

Enfoque: 
Para resolver el problema, siga los pasos a continuación: 
 

• Guarde ‘1’ en curr inicialmente.
• Recorra S y encuentre la primera ocurrencia de curr . Aumente el conteo cuando se encuentre curr . Almacene ‘0’ si curr es ‘1’ o viceversa.
• Repita el paso anterior para todo el recorrido de S.
• El valor final de la cuenta da la respuesta requerida.

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

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of minimum flips required
int minFlips(string target)
{
    char curr = '1';
    int count = 0;
    for(int i = 0; i < target.length(); i++)
    {
         
       // If curr occurs in the final string
       if (target[i] == curr)
       {
           count++;
            
           // Switch curr to '0' if '1'
           // or vice-versa
           curr = (char)(48 + (curr + 1) % 2);
       }
    }
    return count;
}
 
// Driver Code
int main()
{
    string S = "011000";
     
    cout << (minFlips(S));
}
 
// This code is contributed by rock_cool

// Java program for the above approach
import java.util.Arrays;
 
public class GFG {
    // Function to return the count of
    // minimum flips required
    public static int minFlips(String target)
    {
 
        char curr = '1';
        int count = 0;
        for (int i = 0; i < target.length(); i++) {
 
            // If curr occurs in the final string
            if (target.charAt(i) == curr) {
 
                count++;
 
                // Switch curr to '0' if '1'
                // or vice-versa
                curr = (char)(48 + (curr + 1) % 2);
            }
        }
 
        return count;
    }
 
    // Driver Code
    public static void main(String args[])
    {
 
        String S = "011000";
        System.out.println(minFlips(S));
    }
}

# Python3 program for the above approach
 
# Function to return the count
# of minimum flips required
def minFlips(target):
 
    curr = '1'
    count = 0
     
    for i in range(len(target)):
         
        # If curr occurs in the final string
        if (target[i] == curr):
            count += 1
             
            # Switch curr to '0' if '1'
            # or vice-versa
            curr = chr(48 + (ord(curr) + 1) % 2)
     
    return count
 
# Driver Code
if __name__ == "__main__":
     
    S = "011000"
     
    print(minFlips(S))
 
# This code is contributed by chitranayal

// C# program for the above approach
using System;
 
class GFG{
     
// Function to return the count of
// minimum flips required
public static int minFlips(String target)
{
    char curr = '1';
    int count = 0;
    for(int i = 0; i < target.Length; i++)
    {
         
       // If curr occurs in the readonly string
       if (target[i] == curr)
       {
           count++;
            
           // Switch curr to '0' if '1'
           // or vice-versa
           curr = (char)(48 + (curr + 1) % 2);
       }
    }
    return count;
}
 
// Driver code
public static void Main(String []args)
{
    String S = "011000";
    Console.WriteLine(minFlips(S));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
    // Javascript program for the above approach
     
    // Function to return the count
    // of minimum flips required
    function minFlips(target)
    {
        let curr = '1';
        let count = 0;
        for(let i = 0; i < target.length; i++)
        {
 
           // If curr occurs in the final string
           if (target[i] == curr)
           {
               count++;
 
               // Switch curr to '0' if '1'
               // or vice-versa
               curr = String.fromCharCode(48 + (curr.charCodeAt() + 1) % 2);
           }
        }
        return count;
    }
     
    let S = "011000";
       
    document.write(minFlips(S));
     
</script>

2

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