1404. number of steps to reduce binary representation to 1

introduce

Give you a number in binary form s . Please go back and reduce it to 1 Number of steps required ：

• If the current number is even , Divide it by 2 .
• If the current number is odd , Then add 1 .

The title ensures that you can always change the test case into 1 .

Example

Input ：s = “1101”
Output ：6
explain ：“1101” Represents a decimal number 13 .
Step 1) 13 Is odd , Add 1 obtain 14
Step 2) 14 It's even , except 2 obtain 7
Step 3) 7 Is odd , Add 1 obtain 8
Step 4) 8 It's even , except 2 obtain 4
Step 5) 4 It's even , except 2 obtain 2
Step 6) 2 It's even , except 2 obtain 1

Input ：s = “10”
Output ：1
explain ：“10” Represents a decimal number 2 .
Step 1) 2 It's even , except 2 obtain 1

Input ：s = “1”
Output ：0

Answer key

There is a method called simulation , Directly simulate the practice in the topic , Count , To 1 Jump out of

• If the current number is even , Divide it by $2$. When $s$ For binary representation , It is equivalent to removing the end of $0$

• If the current number is odd , Then add $1$. When $s$ For binary representation , It is equivalent to adding... To the last bit $1$（ Pay attention to carry requirements ）

class Solution {
    
public:
    int numSteps(string s) {
    
        int steps = 0;
        while (s != "1") {
    
        	// Count 
            ++steps;
            if (s.back() == '0') {
    
                //  Even numbers 
                s.pop_back();
            }
            else {
    
                //  First step ： Find the lowest  0
                //  The second step ： Put this  0  become  1, And all the following  1  become  0, That's it  +1
                //  Specially , If  s  All of them  1, Then there will be extra carry 
                for (int i = s.size() - 1; i >= 0; --i) {
    
                    if (s[i] == '1') {
    
                        s[i] = '0';
                        if (i == 0) {
    
                            s = "1" + s;
                            break;
                        }
                    }
                    else {
    
                        s[i] = '1';
                        break;
                    }
                }
            }
        }
        return steps;
    }
};

Another solution

• If the last one is 0（ even numbers ）, Then move directly to the right （ except 2）
• If the last one is 1（ Odd number ）, You need to add one , Reaction on a binary string is equivalent to constant carry , Take a few examples

11001 -> 11010 -> 1101
1011 -> 1100 -> 110 -> 11

As can be seen from the above example , A phased operation we can do is ： Add 1 after , Will end with 0 All removed , The total number of steps required is : 1( carry ) + Continuous from the current bit 1 The number of ( It is equivalent to how many new... Are generated at the end of carry 0)

class Solution {
    
public:
    int numSteps(string s) {
    
        int idx = s.size()-1;
        int ans = 0;
        while(idx > 0)// The first place must be left at last 1, Not calculated separately 
        {
    
            if(s[idx] == '0')
            {
    
                ans++;
                idx--;
            }
            else
            {
    
                // carry +1
                ans++;
                while(idx >= 0 && s[idx] == '1')// After carry , Continuous carry （ There may be 1111->10000 The situation of ）
                {
    
                    ans++;
                    idx--;
                }
                if(idx > 0)
                    s[idx]='1';
            }
        }
        return ans;
    }
};