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

LeetCode Number of Steps to Reduce a Number in Binary Representation to One (Problem 1404) gives you the binary representation of an integer as a string s. You need to return the number of steps to reduce it to "1" using two rules: if the current number is even, divide it by 2. If the current number is odd, add 1 to it.

For example, when s = "1101" (decimal 13), you need 6 steps. The number bounces between odd and even values, shrinking until it reaches 1.

Why you cannot just convert to an integer

The binary string can be up to 500 characters long. That is way beyond what a 64-bit integer can hold. You need to work with the string directly, not convert it to a number first.

The good news: the two operations have simple effects on binary strings. Dividing by 2 just removes the last bit (a right shift). Adding 1 to an odd number flips the last bit from 1 to 0 and may propagate a carry upward.

The key insight: process bits right to left

Instead of simulating each step by modifying the string, you can scan the bits from right to left (skipping the leading 1) and count steps directly. You maintain a carry that tracks whether a previous addition propagated.

For each bit position (going right to left, stopping before the leading bit):

• Compute the effective bit: original bit + carry
• If the effective bit is even (0 or 2): you just divide by 2. That is 1 step. If the effective bit was 2, the carry stays 1 (since 0 + carry of 1 from the "add" would produce 2, which is 10 in binary, so the digit becomes 0 and carry is 1).
• If the effective bit is odd (1): you add 1 (making it even with a carry), then divide by 2. That is 2 steps. The carry becomes 1.

At the end, if carry is 1, the leading bit becomes 10, which needs one more divide-by-2 step.

Python solution

def num_steps(s: str) -> int:
    steps = 0
    carry = 0
    for i in range(len(s) - 1, 0, -1):
        bit = int(s[i]) + carry
        if bit % 2 == 1:
            steps += 2
            carry = 1
        else:
            steps += 1
    return steps + carry

Step-by-step walkthrough

Let's trace through s = "1101" (decimal 13) using the actual simulation. The answer is 6 steps.

Each step either halves the number (when even) or increments it by 1 (when odd). Odd steps always produce an even number, so an odd step is always followed by at least one even step. This is why odd bits in the scan cost 2 steps (add 1, then divide) while even bits cost just 1 (divide only).

Complexity analysis

You scan each bit exactly once from right to left. Each iteration does constant work: one addition, one modulo check, and a few increments. The carry variable is the only extra state.

Building blocks

This problem decomposes into two reusable building blocks that CodeBricks drills independently:

Binary string simulation

Working with binary representations as strings instead of integers. You need to understand what dividing by 2 and adding 1 look like at the bit level. Dividing by 2 removes the last bit. Adding 1 to an odd number flips the last bit and may carry. These operations are the foundation of many binary string problems.

Carry propagation

Tracking a carry bit through a sequence of operations. This is the same idea as in binary addition: when a bit overflows (1 + 1 = 10 in binary), the carry propagates to the next position. Here, adding 1 to a bit that is already 1 produces a 0 with a carry of 1. Recognizing carry propagation lets you avoid modifying the string and instead process it in a single pass.

# Core pattern: scan bits right to left with carry
carry = 0
for i in range(len(s) - 1, 0, -1):
    bit = int(s[i]) + carry
    if bit % 2 == 1:
        steps += 2
        carry = 1
    else:
        steps += 1

Once you can fluently handle carry propagation in binary strings, this problem becomes a direct single-pass scan.

Edge cases

s = "1". The number is already 1. The loop body never executes because the range is empty (from index 0 to 0, exclusive). steps stays 0 and carry stays 0, so the function returns 0.

s = "10". Decimal 2. The loop runs once for index 1 (the last bit, which is 0). The effective bit is 0, so steps becomes 1. The carry stays 0. The function returns 1. Indeed, 2 is even, so one division gives 1.

All ones, like "1111". Decimal 15. Every bit except the leading one is 1. The first 1 encountered costs 2 steps and sets carry to 1. Each subsequent 1 has an effective bit of 2 (even), costing 1 step each and keeping carry at 1. At the end, carry is 1, adding one more step. The total is 2 + 1 + 1 + 1 = 5, which matches: 15 -> 16 -> 8 -> 4 -> 2 -> 1.

Very long strings. Since the solution is O(n) with O(1) space, it handles strings up to the constraint limit of 500 characters with no issues.

From understanding to recall

The insight here is that you do not need to simulate the operations step by step. You can process the binary string in a single right-to-left pass, counting steps and tracking carry. The recall cue: "odd bits cost 2 steps and set carry, even bits cost 1 step, add carry at the end."

Spaced repetition locks this in. You write the loop from scratch today, then again in a few days, then a week later. Each time, the carry propagation logic becomes more automatic. When you see a similar binary string simulation problem, the right-to-left scan with carry will surface immediately.

Related posts

• Number of 1 Bits - Another bit manipulation problem that processes bits one at a time. Uses n & (n - 1) to clear set bits. Both problems require understanding how individual bit operations affect the whole number.
• Reverse Bits - Reverses the bit pattern of a 32-bit integer. Like this problem, it processes bits positionally, but in the opposite direction. A good companion for building fluency with bit-level operations.
• Counting Bits - Uses i >> 1 to relate each number's popcount to a smaller number's. Another problem where understanding binary representation at the bit level unlocks an elegant solution.