Problem Description

You are given a non-negative integer num. Your task is to return the number of steps required to reduce num to zero. In each step, if the current number is even, you must divide it by 2; if it is odd, you must subtract 1 from it. Repeat this process until the number becomes zero, and return the count of steps taken.

• Input: A single integer num (0 ≤ num ≤ 10⁶).
• Output: An integer representing the number of steps to reduce num to zero.
• Constraints: Always one valid sequence of steps per input. No extra constraints about reusing elements or multiple solutions.

Thought Process

At first glance, this problem seems straightforward: you simply follow the rules given, step by step, until you reach zero. The most direct way is to simulate the process:

• If the number is even, divide it by 2.
• If the number is odd, subtract 1.
• Count each operation as a step.

The brute-force approach is to use a loop, repeatedly updating the number and incrementing a counter, until the number reaches zero. Since each operation either halves the number or decreases it by one, we can be confident this process will terminate quickly.

Before coding, you might wonder if there's a shortcut or mathematical formula. But since the rules are simple and the input range is moderate, simulating the process is both efficient and easy to understand. There’s no need for optimization beyond a basic loop.

Solution Approach

Let's break down the solution step by step:

1. Initialize a step counter: Start with steps = 0 to count the number of operations.
2. Loop until zero: Use a loop to repeatedly process num until it becomes zero.
3. Check even or odd:
   • If num is even (num % 2 == 0), divide by 2.
   • If num is odd, subtract 1.
4. Increment steps: After each operation, increase the step counter by one.
5. Return the result: When num reaches zero, return the step count.

This approach is efficient because each operation reduces the number quickly—either by halving (for even numbers) or by getting closer to an even number (for odd numbers).

Example Walkthrough

Let's walk through the process with a sample input: num = 14.

1. Start with num = 14, steps = 0.
2. 14 is even: 14 / 2 = 7. steps = 1.
3. 7 is odd: 7 - 1 = 6. steps = 2.
4. 6 is even: 6 / 2 = 3. steps = 3.
5. 3 is odd: 3 - 1 = 2. steps = 4.
6. 2 is even: 2 / 2 = 1. steps = 5.
7. 1 is odd: 1 - 1 = 0. steps = 6.

So, the answer for num = 14 is 6 steps.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(log n). Each division by 2 (for even numbers) halves the number, and subtraction (for odd numbers) only occurs once before the next division. Thus, the number of steps is proportional to the number of bits in num.
  • Space Complexity: O(1). Only a few variables are used for counting steps and updating num.
• Optimized approach:
  • There is no significant optimization beyond the direct simulation loop, as each step is determined by the number’s bits.

Summary

To solve the "Number of Steps to Reduce a Number to Zero" problem, we simply simulate the process of dividing by 2 for even numbers and subtracting 1 for odd numbers, counting each operation until we reach zero. This approach is both intuitive and efficient, with a time complexity of O(log n) and constant space usage. The elegance of the solution lies in its simplicity—by directly following the problem’s rules, we arrive at an optimal and readable solution.

Code Implementation

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
      

class Solution {
public:
    int numberOfSteps(int num) {
        int steps = 0;
        while (num != 0) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                num -= 1;
            }
            steps++;
        }
        return steps;
    }
};
      

class Solution {
    public int numberOfSteps(int num) {
        int steps = 0;
        while (num != 0) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                num -= 1;
            }
            steps++;
        }
        return steps;
    }
}
      

var numberOfSteps = function(num) {
    let steps = 0;
    while (num !== 0) {
        if (num % 2 === 0) {
            num = Math.floor(num / 2);
        } else {
            num -= 1;
        }
        steps++;
    }
    return steps;
};