Number of Steps to Reduce a Number in Binary Representation to One

Given a number s in their binary representation. 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’s guaranteed that you can always reach to one for all testcases.

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’

Hints:
Read the string from right to left, if the string ends in ‘0’ then the number is even otherwise it is odd.
Simulate the steps described in the binary string.

Manipulate the Binary String in C++ Iteratively

The input size of the binary string can be up to 500, thus it is not feasible to convert the number into an integer, as it will not be enough to hold a binary string of length 500 in a 8-byte integer.

Luckily we know that if a binary is even, the last digit should be 0, and dividing it by two, meaning to remove the zero. On another hand, if the binary is odd, we have to add 1 and carry over to the left.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int numSteps(string s) {
        int r = 0;
        while (s != "1") {
            if (s.back() == '0') {
                s.pop_back();
            } else {
                int c = 1;
                int j = s.size() - 2;
                s[j + 1] = '0';
                while ((j >= 0) && (c > 0)) {
                    int x = s[j] - '0' + c;
                    c = x / 2;
                    s[j] = (x % 2 == 0) ? '0' : '1';
                    j --;
                }
                if (c > 0) {
                    s = '1' + s;
                }
            }
            r ++;
        }
        return r;
    }
};

class Solution {
public:
    int numSteps(string s) {
        int r = 0;
        while (s != "1") {
            if (s.back() == '0') {
                s.pop_back();
            } else {
                int c = 1;
                int j = s.size() - 2;
                s[j + 1] = '0';
                while ((j >= 0) && (c > 0)) {
                    int x = s[j] - '0' + c;
                    c = x / 2;
                    s[j] = (x % 2 == 0) ? '0' : '1';
                    j --;
                }
                if (c > 0) {
                    s = '1' + s;
                }
            }
            r ++;
        }
        return r;
    }
};

We simulate the process until the binary string becomes 1 – then we return the number of steps.

–EOF (The Ultimate Computing & Technology Blog) —