Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

We can simulate the reduction from the least significant bit without constructing the potentially huge integer. An effective zero needs one division by two. An effective one needs an increment followed by a division, creating a carry into the remaining prefix.

Approach

Scan all bits except the leading one from right to left, adding the carried bit. If the effective value is one, count two operations and set the carry. If it is zero or two, count one division; an existing carry remains when the effective value is two. After the scan, add one operation if a carry reaches the leading bit. The input 1 needs zero operations and naturally skips the loop.

class Solution:
    def numSteps(self, s: str) -> int:
        n = len(s)
        carry = 0
        res = 0

        for i in range(n - 1, 0, -1):
            curr = int(s[i]) + carry
            if curr == 1:
                res += 2
                carry = 1
            else:
                res += 1

        return res + carry

Complexity analysis

For n = s.length, the right-to-left carry simulation examines each bit once, so it uses O(n) time and O(1) auxiliary space.