Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4

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:

1
2

Input: s = "1"
Output: 0

Solution

Method 1 - Carry Forward

We have already seen similar problem Number of Steps to Reduce a Number to Zero, and use bits operation to solve it method 1.

We know in binary representation, if:

  • Number is odd, the last or rightmost bit is 1. For eg. 111 is 7 an odd number
  • Number is even, the last or rightmost bit is 0. For eg. 1000 is 8 an even number

Algorithm

  • Now, we will start processing the binary string from right to left, bit by bit, aka i = [n-1..1]
  • Because for odd numbers, we have to add 1, we can define a carry variable
  • Now, for each s[i]
    • If s[i] + carry == 1 -> It’s an odd number, we need 2 operations: Add 1 and Divide by two, ans += 2
    • Else if s[i] + carry == 0 -> It’s an even number, we need 1 operation: Divide by two, ans += 1
  • In the end, if carry still exists, we need to increase the answer by 1

Here is the video explanation:

Code

 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
27

class Solution {
    public int numSteps(String s) {
        int carry = 0;
        int ans = 0;
        for (int i = s.length() - 1; i >= 1; i--) {
	        int dig = s.charAt(i) - '0' + carry;
	        // odd number
            if (dig == 1) {
                carry = 1;
                ans += 2;
            } else if (dig == 0) {
	            carry = 0;
                ans += 1;
            } else if (dig == 2) {
	            carry = 1;
                ans += 1;
            }
        }
        // last digit 1 needs to add a carried over digit 1, 
        // which gives 10 in eg. 1
        // So need one more divide to make it 1, hence 1 more step
        if (carry == 1) {
	        ans++;
        }      
        return ans;
    } 
}

Method 2 - Carry Forward and even simpler

Note that once the carry is set to 1, it is not reset to 0. Hence, we can simplify the code even more.

Code

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

class Solution {
    public int numSteps(String s) {
        int carry = 0;
        int ans = 0;
        for (int i = s.length() - 1; i >= 1; i--) {
            if (s.charAt(i) - '0' + carry == 1) {
                carry = 1;
                ans += 2;
            } else {
                ans += 1;
            }
        }
        // last digit 1 needs to add a carried over digit 1, 
        // which gives 10 in eg. 1
        // So need one more divide to make it 1, hence 1 more step
        if (carry == 1) {
	        ans++;
        }      
        return ans + carry;
    } 
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Dry Run

Suppose, s = 1101

 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
27
28

n = 5
carry = 0
s =     1 1 0 1
index = 0 1 2 3

---

i = 3 
=> s[i] = 1
carry + s[i] = 1 => odd => carry = 1, ans += 2 = 2

---

i = 2
=> s[i] = 0, carry = 1
carry + s[i] = 1 => odd => carry = 1, ans += 2 = 4

---

i = 1
=> s[i] = 1, carry = 1
carry + s[i] = 2 => even => ans += 1 = 5

---

Finally, as  carry = 1, we increment ans += 1 = 6

Return ans as 6