Number of Steps to Reduce a Number to Zero

Difficulty: Easy | Acceptance: 85.80% | Paid: No Topics: Math, Bit Manipulation

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

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

• Examples
• Constraints
• Approach 1: Simulation
• Approach 2: Bit Manipulation
• Approach 3: Recursion

Examples

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

Input: num = 8
Output: 4
Explanation:
Step 1) 8 is even; divide by 2 and obtain 4. 
Step 2) 4 is even; divide by 2 and obtain 2. 
Step 3) 2 is even; divide by 2 and obtain 1. 
Step 4) 1 is odd; subtract 1 and obtain 0.

Input: num = 123
Output: 12

Constraints

0 <= num <= 10⁶

Approach 1: Simulation

Intuition We can directly simulate the process described in the problem statement. We iterate until the number becomes zero, checking if it is even or odd at each step and applying the corresponding operation.

Steps

• Initialize a counter steps to 0.
• Loop while num is greater than 0.
• If num is even, divide it by 2.
• If num is odd, subtract 1 from it.
• Increment steps in every iteration.
• Return steps.

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

Complexity

• Time: O(log n) - In the worst case, we divide by 2 repeatedly.
• Space: O(1) - We only use a few variables.
• Notes: This is the most straightforward approach.

Approach 2: Bit Manipulation

Intuition The operations described correspond directly to binary bit manipulation. Dividing by 2 is a right shift, and subtracting 1 clears the least significant bit (LSB). The total steps equal the number of bits (for shifts) plus the number of 1s (for subtractions).

Steps

• If num is 0, return 0.
• Count the number of 1-bits in num (let’s call it ones).
• Calculate the length of the binary representation of num (let’s call it bits).
• The result is (bits - 1) + ones. We subtract 1 from bits because the most significant bit does not require a shift step to disappear (it is handled by the final subtraction).

class Solution:
    def numberOfSteps(self, num: int) -> int:
        if num == 0:
            return 0
        # bin(num) returns string like '0b101', count '1's
        ones = bin(num).count('1')
        # len(bin(num)) - 2 removes '0b' prefix
        bits = len(bin(num)) - 2
        return (bits - 1) + ones

Complexity

• Time: O(log n) - Converting to binary or counting bits takes time proportional to the number of bits.
• Space: O(1) - Constant extra space (ignoring space for string conversion in JS/TS).
• Notes: This is mathematically the most efficient approach, often faster in practice due to CPU bit-counting instructions.

Approach 3: Recursion

Intuition We can solve the problem using recursion by breaking it down into smaller sub-problems. If the number is even, we solve for num / 2 and add 1 step. If odd, we solve for num - 1 and add 1 step.

Steps

• Base case: if num is 0, return 0.
• If num is even, return 1 + numberOfSteps(num / 2).
• If num is odd, return 1 + numberOfSteps(num - 1).

class Solution:
    def numberOfSteps(self, num: int) -> int:
        if num == 0:
            return 0
        if num % 2 == 0:
            return 1 + self.numberOfSteps(num // 2)
        else:
            return 1 + self.numberOfSteps(num - 1)

Complexity

• Time: O(log n) - Similar to the iterative approach.
• Space: O(log n) - Due to the recursion stack depth.
• Notes: Elegant but less memory-efficient than the iterative approach for very large numbers (though constraints are small here).