Number of Steps to Reduce a Number to Zero - Solution & Explanation
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 have to divide it by 2, otherwise, you have to subtract 1 from it.
Example 1:
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.
Example 2:
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.
Example 3:
Input: num = 123 Output: 12
Constraints:
0 <= num <= 106
Approach Overview
Problem Overview: You are given an integer num. If the number is even, divide it by 2. If it is odd, subtract 1. Repeat until the value becomes 0 and return the total number of operations performed.
Approach 1: Iterative Simulation (O(log n) time, O(1) space)
The most direct approach simulates the operations exactly as described. Start with num and repeatedly apply the rule: if num % 2 == 0, divide by 2; otherwise subtract 1. Each operation reduces the magnitude of the number quickly, especially the division by 2 which removes one binary digit. Because each step either clears the least significant bit or shifts the number right, the loop runs proportional to the number of bits in num, giving O(log n) time. This approach uses constant extra memory and works well in any language.
The key insight comes from bit manipulation. In binary, subtracting 1 removes a trailing 1, and dividing by 2 shifts bits right. That means every 1 bit contributes one subtraction step, while every bit position contributes one division step except the last. This explains why the algorithm runs in logarithmic time relative to the value of num.
Approach 2: Recursive Reduction (O(log n) time, O(log n) space)
The same logic can be expressed recursively. Define a function that returns 0 when num == 0. For other values, perform one operation and call the function on the updated number. If the number is even, recurse with num / 2; otherwise recurse with num - 1. Each recursive call reduces the number toward zero, so the recursion depth equals the number of operations performed.
This version highlights the mathematical structure of the problem and maps naturally to the rules described in the prompt. However, it uses call stack space proportional to the number of steps, which is O(log n). In practice, the iterative version is usually preferred for production code because it avoids recursion overhead.
The problem primarily falls under math reasoning and bit manipulation, since the operations correspond directly to binary properties of the number.
Recommended for interviews: The iterative approach. It is simple, efficient, and demonstrates clear reasoning about how repeated division shrinks the number. Explaining the binary interpretation (each bit causing either a subtract or divide step) shows deeper understanding and often impresses interviewers.
Approach 1: Iterative Approach
In this approach, we use a loop to repetitively apply the given conditions on the number. If the number is even, divide it by 2, and if odd, subtract 1. We count and return the number of operations needed to reduce the number to zero.
The function numberOfSteps iteratively checks if the number is even or odd, performs the respective operation, and increments the step counter until the number reduces to zero. The result is printed in the main function.
Complexity
Time Complexity: O(log n) where n is the initial number.
Space Complexity: O(1), since no additional space is used.
Approach 2: Recursive Approach
This approach uses recursion to handle the problem. The function calls itself with the same logical conditions: divide by 2 for even or subtract 1 for odd, until the base case of zero is reached. It accumulates the count of steps through recursive calls.
This recursive solution involves the function calling itself while reducing the number based on its parity until it terminates on zero, accumulating step count in the process.
Complexity
Time Complexity: O(log n)
Space Complexity: O(log n), considering function call stack for recursion.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(log n) where n is the initial number. |
| Recursive Approach | Time Complexity: O(log n) |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(log n) | O(1) | Best general solution; minimal memory and straightforward implementation |
| Recursive Reduction | O(log n) | O(log n) | Useful for demonstrating the mathematical recurrence or practicing recursion |
Video Solution
Number of Steps to Reduce a Number to Zero | Live Coding with Explanation | Leetcode - 1342 • Algorithms Made Easy • 3,264 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Steps to Reduce a Number to Zero easy or hard?
Number of Steps to Reduce a Number to Zero Python/Java solution
How to solve Number of Steps to Reduce a Number to Zero in O(log n)?
What is the best approach for Number of Steps to Reduce a Number to Zero?
Is Number of Steps to Reduce a Number to Zero asked at Google/Amazon/Meta?
What data structure is used in Number of Steps to Reduce a Number to Zero?
What is the time complexity of Number of Steps to Reduce a Number to Zero?
Ready to solve this problem?
Practice Number of Steps to Reduce a Number to Zero with our built-in code editor and test cases.
Practice on FleetCode