LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One

If you prefer a quick walk through:

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'

Problem Link: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/

Intuition

To solve this question, we need to understand that the last digit of any even binary number is 0, and the last digit of any odd binary number is 1.

To divide an even binary number by 2, we only need to chop the last digit off. For example, 110 divided by 2 is 11, since dividing by 2 means minus one from each power of 2 in 2² + 2¹, which is 2¹ + 2⁰. That is 11 in the binary number.

For any odd binary number, adding 1 turns it into an even number with the last digit 0, and a “one” is carried over to the second last digit. like 101 + 1 = 110. If there isn’t a second last digit, the ‘one’ is carried over and will result in a new bit. Like 1 + 1 = 10.

Example

Suppose we are given the binary number 1101 and wish to reduce it to 1, we do not change the original binary number and instead use a variable ‘carry’ to record the carried-over digit.

We start from the last digit of the binary number.
Since it is odd, we first add one to the number, and a “1” is carried over to the second last digit. Now the number is even, we divide it by 2 by chopping it to 110, with a carried-over digit 1. This takes 2 steps.

Now the number is still odd, we add 1 to it and divide it by 2, so that we have 11 with another carried-over digit 1. This takes 2 steps.

11 with a carried-over digit 1 is even, so dividing 2 means chopping one more digit, which results in 1, with a carried-over digit 1. This takes 1 step.

Now the number only has one digit, the carry digit will result in one more digit to the left and result in the binary string 10.

We know that 10 is an even number, so we divide it by 2 and obtain 1, which is our last step.

So in total 6 steps.

Approach

We first initialize the variable l to be the length of s-1. The variable carry and count are initialized to 0. The function enters into a while loop and reads s from right to left and iterates when l is larger than 0.
If the number is even and carry = 0, the result will be even and divided by 2, so we increment the count by 1 and set carry to 0.
If the number is odd and carry = 1, the result will be even and divided by 2, except we need to carry over a digit. So we increment the count by 1 and set carry to 1.
When the number is even and carry = 1, or when the number is odd and carry = 0, both results will be odd. So we add one to it to make the result even and divide by 2. That takes two steps, so we increment the count by 2 and set carry to 1.
The while loop stops when we reach the first digit of the given binary number, which is always 1. After that, we check the value of the carry. If it is 1, it means that a carried-over digit 1 needs to be added, which gives 10. So we need one more divide to make it 1, which is one more step and increments count by 1.
Finally, the function returns the step counts it takes to reduce the binary number to 1.

class Solution:
    def numSteps(self, s):
        """
        :type s: str
        :rtype: int
        """
        l = len(s) - 1
        carry = 0
        count = 0
        while (l > 0):
            ##even number with carry = 0, result even
            if int(s[l]) + carry == 0:
                carry = 0
                count += 1
            ##odd number with carry = 1, result even
            elif int(s[l]) + carry == 2:
                carry = 1
                count += 1
            ##even number with carry = 1, result odd
            ##odd number with carry = 0, result odd
            else:
                carry = 1
                count += 2
            l -= 1
        #last digit 1 needs to add a carried over digit 1, which gives 10. 
        #So need one more divide to make it 1 (one more step)
        if carry == 1:
            count += 1
        return count

Follow our Youtube channel for new updates:

https://www.youtube.com/@algo.monster

AlgoMonster focuses on both learning and practice. You get everything you need to excel at your technical interviews: a detailed introduction to the key coding patterns, examples and problems, presented in a highly visual and interactive environment. Follow our website for more information:

https://algo.monster/