Problem Statement:

Given the binary representation of an integer as a string s, return the number of steps to reduce it to 1 under the following rules:

If the current number is even, you have to divide it by 2.
If the current number is odd, you have to add 1 to it.

It is guaranteed that you can always reach one for all test cases.

Example 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.

Example 2:

Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.

Example 3:

Input: s = "1"
Output: 0

Constraints:

1 <= s.length <= 500
s consists of characters '0' or '1'
s[0] == '1'

Solution:

How do you add 1 to a binary string A: Go from right to left, if you see a one, make it zero. If you see a zero, make it one and stop. If you could not find zero then create a string like 1000 for 111.

How do you divide a binary string by 2 A: Just right shift by 1.

Now that we have both of these pieces, we can simulate the steps:

 
string add_one(string s, int l)
{
    int i=l-1;
    while (i>=0 && s[i]!='0')
    {
        s[i]='0';
        i--;
    }
    if (i>=0) s[i]='1';
    else s="1"+s;
    return s;
}

string divide_by_two(string s)
{
    return string(s.begin(), s.end()-1);
}

class Solution {
public:
    int numSteps(string s) {
        int ctr=0;
        while (s!="1")
        {
            int l = s.length();
            if (s[l-1]=='0') s = divide_by_two(s);
            else s = add_one(s, l);
            ctr ++;
        }
        return ctr;
    }
};