Number of Steps to Reduce a Number to Zero: Simulation and Bit Tricks

LeetCode 1342. Number of Steps to Reduce a Number to Zero gives you a non-negative integer num and asks how many steps it takes to reduce it to zero. In each step, if the number is even you divide it by 2, and if it is odd you subtract 1. Simple rules, but there is a neat bit manipulation shortcut hiding underneath.

Approach 1: Simulate the process

The most natural approach is to do exactly what the problem says. Loop while num is greater than 0. If it is even, halve it. If it is odd, subtract 1. Count each operation.

def number_of_steps(num: int) -> int:
    steps = 0
    while num > 0:
        if num % 2 == 0:
            num //= 2
        else:
            num -= 1
        steps += 1
    return steps

This is clean and easy to reason about. Every iteration reduces num toward zero, so the loop always terminates.

Step-by-step walkthrough: num = 14

Let's trace through the simulation with num = 14 to see each operation in action.

Six steps and we reach zero. Three divisions (for the even values 14, 6, 2) and three subtractions (for the odd values 7, 3, 1).

Approach 2: Count the bits

Look at the binary representation. Dividing by 2 is the same as a right shift, which removes the lowest bit. Subtracting 1 from an odd number clears the lowest set bit (flipping it from 1 to 0). So every 0 bit in the binary representation contributes one step (a right shift), and every 1 bit contributes two steps (one subtraction to clear it, then one right shift to move past it), except the leading 1 bit which only contributes one subtraction (there is no shift after the final bit is cleared, since the number becomes zero).

That gives us a formula: the total number of steps equals the number of 1 bits plus the total bit length, minus 1 (to avoid counting a shift after the last bit). In other words:

• Each 1 bit costs 2 operations (subtract 1, then shift), except the highest 1 bit costs only 1 (subtract 1, and the number hits zero).
• Each 0 bit costs 1 operation (shift).
• Total = (number of 1 bits) + (bit length) - 1.

def number_of_steps(num: int) -> int:
    if num == 0:
        return 0
    return num.bit_count() + num.bit_length() - 1

This runs in O(1) time (assuming fixed-width integers) and needs no loop at all.

Complexity analysis

Both approaches are fast. The simulation loop runs at most 2 * log2(n) times since each pair of operations (subtract then divide) removes one bit. The bit counting approach skips the loop entirely.

Building blocks

This problem is built from two fundamental patterns that you will see in many other problems.

Simulation

When a problem gives you explicit rules for transforming a value step by step, simulating those rules directly is almost always a valid first approach. You loop, apply the transformation, and count. This same pattern appears in problems like Collatz conjecture variants, state machines, and any "apply rules until termination" problem. The key skill is translating the problem statement into a clean loop with a clear termination condition.

Bit manipulation basics

Recognizing that "divide by 2" is a right shift and "subtract 1 from an odd number" clears the lowest set bit connects this problem to the broader world of bit tricks. Once you see the binary structure, you can often replace a simulation loop with a closed-form expression. The bit_count() and bit_length() built-ins are your friends here. You will use these same tools in Number of 1 Bits, Counting Bits, and Power of Two.

Edge cases

• n = 0: Already zero, so the answer is 0 steps. The simulation loop never runs, and the bit counting approach returns early.
• n = 1: One step. 1 is odd, subtract 1 to get 0. bit_count() = 1, bit_length() = 1, so 1 + 1 - 1 = 1.
• Powers of 2: For n = 8 (binary 1000), there is one 1 bit and the bit length is 4. Steps = 1 + 4 - 1 = 4. That is three right shifts to get from 8 to 1, then one subtraction to reach 0. Only one subtraction is needed because there is only one set bit.

From understanding to recall

You can read through both solutions in a minute, but will you remember the bit counting formula in two weeks? The simulation is easy to reconstruct from the problem statement, but the bit_count() + bit_length() - 1 insight takes deliberate practice to internalize.

Spaced repetition helps you move from "I understand it" to "I can reproduce it." CodeBricks breaks this problem into its two building blocks, the simulation loop and the bit counting formula, and drills them at increasing intervals. After a few review sessions, seeing "reduce to zero" or "count operations on binary" will immediately trigger the right approach.

Related posts

• Number of 1 Bits - Count set bits using n & (n - 1), the same bit counting skill used in the O(1) solution here
• Power of Two - Check if a number has exactly one set bit, another application of understanding binary structure
• Counting Bits - Count set bits for every number from 0 to n, extending the single-number bit counting idea to an entire range