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:

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

Solution

Method 1 - Carry Forward

We have already seen similar problem Number of Steps to Reduce a Number to Zero Problem, 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

Java
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

Java
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

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