Number of Steps to Reduce a Number to Zero — Solution
Number of Steps to Reduce a Number to Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Steps to Reduce a Number to Zero is an easy coding problem on math and bit manipulation, asked in Amazon, Adobe and Cognizant interviews.
- Difficulty: Easy
- Topics: Math, Bit Manipulation
- Asked at: Amazon, Adobe, Cognizant
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer num, return the number of steps needed to reduce it to zero.
In one step, if the current number is even you divide it by two; otherwise you subtract one from it.
Example 1
Input: num = 14
Output: 6
Explanation: 14 → 7 → 6 → 3 → 2 → 1 → 0.
Example 2
Input: num = 8
Output: 4
Explanation: 8 → 4 → 2 → 1 → 0.
Example 3
Input: num = 0
Output: 0
Constraints
0 <= num <= 1000000
Follow-up: In binary, each division is a right shift and each subtraction clears a set bit. Can you answer from the bit pattern alone?
Hints for Number of Steps to Reduce a Number to Zero
Hint 1
Simulate the process directly; it terminates in O(log num) steps.
Hint 2
In binary, halving is a right shift and subtracting one from an odd number clears its lowest bit.
Hint 3
So the answer is (number of bits - 1) + (number of set bits), for num > 0.
How to solve Number of Steps to Reduce a Number to Zero
Simulate the process: halve when even, decrement when odd, and count steps. Each halving removes a bit, so the loop runs O(log num) times.
Approach
- While
num > 0: if even,num //= 2; elsenum -= 1; increment the count. - Return the count.
Why it works
In binary, subtracting one from an odd number clears the lowest bit and halving shifts right, so each set bit costs one decrement and each bit position (except the top) costs one shift. The simulation counts exactly those operations.
Complexity
- Time —
O(log num) - Space —
O(1)
Pitfalls
- The closed form is
(bit length - 1) + popcountfornum > 0;0needs zero steps. - Nothing here overflows — the value only ever decreases.
Reference solution
Python
def numberOfSteps(num: int) -> int:
steps = 0
while num > 0:
num = num // 2 if num % 2 == 0 else num - 1
steps += 1
return stepsJava
public static int numberOfSteps(int num) {
int steps = 0;
while (num > 0) {
num = num % 2 == 0 ? num / 2 : num - 1;
steps++;
}
return steps;
}C++
int numberOfSteps(int num) {
int steps = 0;
while (num > 0) {
num = num % 2 == 0 ? num / 2 : num - 1;
steps++;
}
return steps;
}JavaScript
var numberOfSteps = function(num) {
let steps = 0;
while (num > 0) {
num = num % 2 === 0 ? num / 2 : num - 1;
steps++;
}
return steps;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Bit Manipulation