Número de pasos necesarios para convertir un número binario a uno

Dada una string binaria str , la tarea es imprimir la cantidad de pasos necesarios para convertirla en una mediante las siguientes operaciones: 

1. Si ‘S’ es impar, súmale 1.
2. Si ‘S’ es par, divídelo entre 2.

Ejemplos:

Entrada: str = «1001001» 
Salida: 12

Entrada: str = “101110” 
Salida: 8
El número ‘101110’ es par, después de dividirlo por 2 obtenemos un número impar ‘10111’ por lo que le sumaremos 1. Entonces obtendremos ‘11000’ que es par y se puede dividir tres veces seguidas y obtenemos ’11’ que es impar, sumarle 1 nos dará ‘100’ que es par y se puede dividir 2 veces en una fila. Como resultado, obtenemos 1. 
Entonces, se requirieron 8 veces las dos operaciones anteriores en este número.

A continuación se muestra el algoritmo paso a paso para resolver este problema:  

• Inicialice la string S como un número binario.
• Si el tamaño del binario es 1, entonces el número requerido de acciones será 0.
• Si el último dígito es 0, entonces es un número par, por lo que se requiere una operación para dividirlo por 2.
• Después de encontrar 1, recorra hasta obtener 0, con cada dígito se realizará una operación.
• Después de encontrar 0 después de 1 mientras atraviesa, reemplace 0 por 1 y comience nuevamente desde el paso 4.

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

// C++ program to count the steps
// required to convert a number to 1 
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
// function to calculate the number of actions
int calculate_(string s)
{
    // if the size of binary is 1
    // then the number of actions will be zero
    if (s.size() == 1)
        return 0;
 
    // initializing the number of actions as 0 at first
    int count_ = 0;
    for (int i = s.length() - 1; i > 0;) {
        // start traversing from the last digit
        // if its 0 increment the count and decrement i
        if (s[i] == '0') {
            count_++;
            i--;
        }
        // if s[i] == '1'
        else {
            count_++;
 
            // stop until you get 0 in the binary
            while (s[i] == '1' && i > 0) {
                count_++;
                i--;
            }
            if (i == 0)
                count_++;
 
            // when encounter a 0 replace it with 1
            s[i] = '1';
        }
    }
    return count_;
}
 
// Driver code
int main()
{
    string s;
    s = "10000100000";
 
    cout <<  calculate_(s);
    return 0;
}

//Java program to count the steps
//required to convert a number to 1
 
public class ACX {
 
    //function to calculate the number of actions
    static int calculate_(String s)
    {
     // if the size of binary is 1
     // then the number of actions will be zero
     if (s.length() == 1)
         return 0;
 
     // initializing the number of actions as 0 at first
     int count_ = 0;
     char[] s1=s.toCharArray();
     for (int i = s.length() - 1; i > 0😉 {
         // start traversing from the last digit
         // if its 0 increment the count and decrement i
         if (s1[i] == '0') {
             count_++;
             i--;
         }
         // if s[i] == '1'
         else {
             count_++;
 
             // stop until you get 0 in the binary
             while (s1[i] == '1' && i > 0) {
                 count_++;
                 i--;
             }
             if (i == 0)
                 count_++;
 
             // when encounter a 0 replace it with 1
             s1[i] = '1';
         }
     }
     return count_;
    }
 
    //Driver code
    public static void main(String []args)
    {
         
         String s;
         s = "10000100000";
 
         System.out.println(calculate_(s));
 
    }
}

# Python3 program to count the steps
# required to convert a number to 1
 
# Method to calculate the number of actions
def calculate_(s):
     
    # if the size of binary is 1
    # then the number of actions will be zero
    if len(s) == 1:
        return 0
 
    # initializing the number of actions as 0 at first
    count_ = 0
    i = len(s) - 1
    while i > 0:
         
        # start traversing from the last digit
        # if its 0 increment the count and decrement i
        if s[i] == '0':
            count_ += 1
            i -= 1
             
            # if s[i] == '1'
        else:
            count_ += 1
             
            # stop until you get 0 in the binary
            while s[i] == '1' and i > 0:
                count_ += 1
                i -= 1
            if i == 0:
                count_ += 1
            # when encounter a 0 replace it with 1
            s = s[:i] + "1" + s[i + 1:]
    return count_
 
# Driver code
s = "10000100000"
print(calculate_(s))
     
# This code is contributed by
# Rajnis09

// C# program to count the steps
//required to convert a number to 1
using System;
class GFG
{
 
    // function to calculate the number of actions
    static int calculate_(String s)
    {
        // if the size of binary is 1
        // then the number of actions will be zero
        if (s.Length == 1)
            return 0;
     
        // initializing the number of actions as 0 at first
        int count_ = 0;
        char[] s1 = s.ToCharArray();
        for (int i = s.Length - 1; i > 0;)
        {
            // start traversing from the last digit
            // if its 0 increment the count and decrement i
            if (s1[i] == '0')
            {
                count_++;
                i--;
            }
             
            // if s[i] == '1'
            else
            {
                count_++;
     
                // stop until you get 0 in the binary
                while (s1[i] == '1' && i > 0)
                {
                    count_++;
                    i--;
                }
                if (i == 0)
                    count_++;
     
                // when encounter a 0 replace it with 1
                s1[i] = '1';
            }
        }
        return count_;
    }
 
    // Driver code
    public static void Main(String []args)
    {
        String s;
        s = "10000100000";
 
        Console.WriteLine(calculate_(s));
    }
}
 
// This code is contributed by princiraj1992

<?php
// PHP program to count the steps
// required to convert a number to 1
 
// function to calculate the
// number of actions
function calculate_($s)
{
    // if the size of binary is 1
    // then the number of actions
    // will be zero
    if (strlen($s) == 1)
        return 0;
 
    // initializing the number of
    // actions as 0 at first
    $count_ = 0;
    for ($i = strlen($s) - 1; $i > 0;)
    {
        // start traversing from the last
        // digit if its 0 increment the
        // count and decrement i
        if ($s[$i] == '0')
        {
            $count_++;
            $i--;
        }
         
        // if $s[$i] == '1'
        else
        {
            $count_++;
 
            // stop until you get 0 in the binary
            while ($s[$i] == '1' && $i > 0)
            {
                $count_++;
                $i--;
            }
            if ($i == 0)
                $count_++;
 
            // when encounter a 0 replace
            // it with 1
            $s[$i] = '1';
        }
    }
    return $count_;
}
 
// Driver code
 
$s = "10000100000";
echo calculate_($s);
 
// This code is contributed
// by Shivi_Aggarwal
?>

<script>
 
// Javascript program to count the steps
// required to convert a number to 1
     
// Function to calculate the number of actions
function calculate_(s)
{
     
    // If the size of binary is 1
    // then the number of actions
    // will be zero
    if (s.length == 1)
        return 0;
     
    // Initializing the number of
    // actions as 0 at first
    let count_ = 0;
    let s1 = s.split("")
     
    for(let i = s.length - 1; i > 0;)
    {
         
        // Start traversing from the last
        // digit if its 0 increment the
        // count and decrement i
        if (s1[i] == '0')
        {
            count_++;
            i--;
        }
         
        // If s[i] == '1'
        else
        {
            count_++;
             
            // Stop until you get 0 in the binary
            while (s1[i] == '1' && i > 0)
            {
                count_++;
                i--;
            }
            if (i == 0)
                count_++;
             
            // When encounter a 0
            // replace it with 1
            s1[i] = '1';
        }
    }
    return count_;
}
 
// Driver code
let s = "10000100000";
 
document.write(calculate_(s));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

16