Number of Steps to Reduce a Number to Zero
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem statement. We use a loop that continues as long as the number is greater than zero. Inside the loop, we check if the number is even or odd and perform the corresponding operation (divide by 2 or subtract 1). We increment a counter in each iteration to keep track of the steps.
Algorithm
- Initialize a variable
stepsto 0. - If
numis 0, return 0. - Loop while
numis greater than 0:- If
numis even (i.e.,num % 2 == 0), updatenumby dividing it by 2 (num = num / 2). - Else (if
numis odd), updatenumby subtracting 1 from it (num = num - 1). - Increment the
stepscounter in each iteration.
- If
- After the loop terminates, return the total
steps.
Walkthrough
The most straightforward way to solve this problem is to follow the instructions literally. We can set up a loop that runs until our number becomes zero. In each step of the loop, we check if the current number is even or odd.
- If the number is even, we divide it by 2.
- If the number is odd, we subtract 1 from it.
We use a counter variable, initialized to zero, and increment it for every operation we perform. The loop terminates when the number reaches zero, and we return the value of the counter.
This can be implemented using standard arithmetic operators (% for modulo and / for division) or slightly more efficient bitwise operators (& to check for odd/even and >> for division by 2).
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; }}Here is the version with bitwise operators, which is typically faster at the machine level:
class Solution { public int numberOfSteps(int num) { int steps = 0; while (num > 0) { if ((num & 1) == 0) { // Check if the last bit is 0 (even) num >>= 1; // Right shift by 1 (divide by 2) } else { num--; // Subtract 1 } steps++; } return steps; }}Complexity
Time
O(log n) - The value of `num` is reduced by at least half in every two steps. For an even number, it's halved in one step. For an odd number, it becomes even in one step and is then halved in the next. The number of operations is therefore proportional to the number of bits in the binary representation of `num`, which is `log2(num)`.
Space
O(1) - We only use a few variables to store the current number and the step count, which requires constant extra space regardless of the input size.
Trade-offs
Pros
Very simple to understand and implement as it directly translates the problem description into code.
It is guaranteed to be correct and works for all non-negative integers.
Cons
Slightly less performant than the bit manipulation approach due to the overhead of the loop and conditional checks in each iteration.
Solutions
Solution
class Solution {public int numberOfSteps(int num) { int ans = 0; while (num != 0) { num = (num & 1) == 1 ? num - 1 : num >> 1; ++ans; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.