Number of Steps to Reduce a Number in Binary Representation to One — LeetCode 1404 Python Solution

MediumBit ManipulationStringSimulation

Problem: #1404
Pattern: Bit Manipulation
Reading time: 4 min
Source: leetcode.com

The 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.

Example

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.

Python solution

Python

class Solution:
    def numSteps(self, s: str) -> int:
        carry = False
        ans = 0
        for c in s[:0:-1]:
            if carry:
                if c == '0':
                    c = '1'
                    carry = False
                else:
                    c = '0'
            if c == '1':
                ans += 1
                carry = True
            ans += 1
        if carry:
            ans += 1
        return ans

Complexity

Measure	Complexity
Time	O(n), where n is the length of the string s
Space	O(1) auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One?: LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One is rated Medium on LeetCode.
What is the time complexity of LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One?: The Python solution on this page runs in O(n), where n is the length of the string s.
What is the space complexity of LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One cover?: LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One is tagged Bit Manipulation, String and Simulation on LeetCode.