1342 - Number of Steps to Reduce a Number to Zero

Difficulty: Easy | Pattern: Math / Bit Manipulation | Company tags: Amazon, Google

Problem Statement

Given an integer num, return the number of steps to reduce it to zero.

In one step, if the current number is even, you divide it by 2; otherwise, you subtract 1 from it.

Example 1:

Input: num = 14
Output: 6
Explanation:
14 → 7 (÷2) → 6 (-1) → 3 (÷2) → 2 (-1) → 1 (÷2) → 0 (-1) = 6 steps

Example 2:

Input: num = 8
Output: 4  (8→4→2→1→0)

Example 3:

Input: num = 123
Output: 12

Approach 1: Simulation — O(log n)

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

Approach 2: Bit Counting — O(log n)

Key insight: In binary, each bit represents one operation:

• 1 bit → subtract 1 (clears the bit) then an additional divide-2
• 0 bit → just divide by 2

For a number with b bits (binary length) and s set bits:

• Subtract 1 for each set bit: s steps
• Divide by 2 to shift right: b - 1 steps (one for each bit position except last)
• But the last bit (1) only needs 1 subtract, not an extra divide

Total: (b - 1) + s

def numberOfSteps(num: int) -> int:
    b = num.bit_length()    # number of bits
    s = bin(num).count('1') # number of set bits
    return (b - 1) + s

Algorithm Flow

Dry Run

num = 14 (binary: 1110)

Step	num	even?	action
1	14	yes	14 ÷ 2 = 7
2	7	no	7 - 1 = 6
3	6	yes	6 ÷ 2 = 3
4	3	no	3 - 1 = 2
5	2	yes	2 ÷ 2 = 1
6	1	no	1 - 1 = 0

6 steps ✓

Bit method: 14 = 1110 → b=4, s=3 → (4-1)+3 = 6 ✓

Edge Cases

• num = 0 → 0 steps
• num = 1 → 1 step (subtract 1)
• Powers of 2 → log₂n + 1 steps (all divides, then one subtract)

Complexity

• Time: O(log n) — number halves (or decreases by 1 then halves) each time
• Space: O(1)

Key Terms

Term	Definition
Bit length	Number of bits needed to represent a positive integer in binary (num.bit_length()).
Set bit (popcount)	A bit equal to 1 in a number's binary representation; the count of such bits is the "popcount".
Simulation	Directly following the problem's described process step by step rather than deriving a closed form.
Closed-form / bit-counting trick	Deriving the answer directly from bit-length and popcount instead of looping through each operation.

FAQ

Q1: Why does (bit_length - 1) + popcount give the exact step count? Every bit position except the leading 1 requires exactly one divide-by-2 (right shift), contributing b - 1 steps. Every set bit additionally requires one subtract-1 to clear it before it can be shifted away, contributing s steps. Summing gives the total.

Q2: Why is num = 0 a special case? The loop condition is num > 0, so if num starts at 0, the loop body never executes and the answer is 0 steps — no operation is needed.

Q3: Is the bit-counting approach faster than simulation in practice? Both are O(log n) asymptotically, but bit-counting does O(1) work per bit using built-in bit_length()/popcount (often hardware-accelerated), while simulation does a division or subtraction every iteration — bit-counting is typically faster in practice despite the same big-O.

Q4: What if the operations were reversed (halve first, then decide even/odd)? The problem defines a strict order (check even/odd, then act), so changing the order changes the recurrence entirely — this is a different problem, not equivalent to a simple relabeling.

Q5: How would you extend this to count steps for reducing to zero using operations mod 3 (divide by 3 if divisible, else subtract 1)? The elegant bit-trick relies on binary structure and doesn't generalize to base 3; you'd fall back to simulation or a base-3 digit-based analog with careful per-digit accounting.

Quick Revision

• Two valid approaches: direct simulation, or a closed-form bit-counting formula.
• Simulation: while num > 0, halve if even, else subtract 1; count each iteration.
• Bit-counting formula: steps = (bit_length(num) - 1) + popcount(num).
• Intuition: bit_length - 1 counts the divide-by-2 shifts; popcount counts the subtract-1 operations for each set bit.
• Edge case: num = 0 → 0 steps (loop never runs).
• Edge case: powers of 2 → exactly log2(num) + 1 steps (all divides plus one final subtract).
• Both approaches run in O(log n) time and O(1) space.
• Verify formula against simulation on a small example (e.g. 14 → 6 steps) before trusting it in an interview.

Related Problems

• 191 - Number of 1 Bits — same popcount building block.
• 231 - Power of Two — related bit-length/single-set-bit reasoning.
• Pattern: bit-manipulation problems solvable via bit_length() and popcount instead of simulation.