LC-1404 Medium LeetCode

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

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 61% Topics: String, Bit Manipulation, Simulation

Reading material

Strings 12 min Bit Manipulation 10 min Simulation & Enumeration 9 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def numSteps(self, s):
        """
        :type s: str
        :rtype: int
        """
        result, carry = 0, 0
        for i in reversed(xrange(1, len(s))):
            if int(s[i]) + carry == 1:
                carry = 1  # once it was set, it would keep carrying forever
                result += 2
            else:
                result += 1
        return result+carry

Solution from kamyu104/LeetCode-Solutions · MIT