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.
This approach analyzes the problem from a binary representation perspective. By observing the effect of the operations on the bits of the number, we can derive a mathematical formula to calculate the number of steps directly. This avoids the simulation loop and leads to a highly efficient, constant-time solution.
Algorithm
- Handle the edge case: if
numis 0, return 0. - Calculate the number of set bits (1s) in the binary representation of
num. In Java, this isInteger.bitCount(num). - Calculate the length of the binary representation of
num. This can be found usingInteger.toBinaryString(num).length()or more efficiently32 - Integer.numberOfLeadingZeros(num). - The total number of steps is given by the formula:
(length of binary string) + (number of set bits) - 1. - Return this calculated value.
Walkthrough
A deeper look at the operations reveals a pattern related to the number's binary form.
- Dividing by 2: This is equivalent to a right bit shift (
>> 1). This operation is performed when the number is even, i.e., its least significant bit (LSB) is0. - Subtracting 1: This is performed when the number is odd (LSB is
1). Subtracting 1 from an odd number flips its LSB from1to0, making it even. The next operation will then be a division by 2.
Let's analyze the cost per bit:
- A
0bit at the end of the binary string requires one step (division/right shift) to be removed. - A
1bit at the end requires two steps: one step to subtract 1 (making it0), and another step to divide by 2 (right shift). The only exception is the most significant bit (MSB), which, when it becomes the number1, only requires one subtraction step to become0.
This leads to a formula: the total steps are the sum of steps for each bit. Each 0 contributes 1 step, and each 1 contributes 2 steps, minus 1 for the final step on the MSB.
Total Steps = (number of 0s) * 1 + (number of 1s) * 2 - 1
Let L be the length of the binary string and P be the population count (number of 1s). The number of 0s is L - P.
Total Steps = (L - P) + 2*P - 1 = L + P - 1.
So, the formula is: (length of binary representation) + (number of set bits) - 1.
For a positive number num, the length of its binary representation is floor(log2(num)) + 1 and the number of set bits is its population count.
class Solution { public int numberOfSteps(int num) { if (num == 0) { return 0; } // Using Integer.toBinaryString() to get length and Integer.bitCount() for set bits. String binaryString = Integer.toBinaryString(num); int length = binaryString.length(); int setBits = Integer.bitCount(num); return length + setBits - 1; }}For maximum performance, we can avoid string conversion by using other bitwise intrinsics:
class Solution { public int numberOfSteps(int num) { if (num == 0) { return 0; } // Length of binary string for a 32-bit int is 32 - numberOfLeadingZeros. int length = 32 - Integer.numberOfLeadingZeros(num); int setBits = Integer.bitCount(num); return length + setBits - 1; }}Complexity
Time
O(1) - The built-in functions `Integer.bitCount` and `Integer.numberOfLeadingZeros` are typically implemented using single, fast hardware instructions. Therefore, the calculation is independent of the magnitude of `num` (for a fixed-size integer type) and executes in constant time.
Space
O(1) - This approach uses a fixed number of variables. The built-in functions operate in constant space. (Note: `Integer.toBinaryString` would technically use O(log n) space for the string, but the version with `numberOfLeadingZeros` is purely O(1)).
Trade-offs
Pros
Extremely fast and efficient, as it computes the result directly without loops.
Provides a deeper understanding of the problem at the bit level.
Cons
The logic is less intuitive and requires understanding binary arithmetic.
It relies on built-in functions whose implementation details might not be obvious to everyone.
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; }}class Solution {public: int numberOfSteps(int num) { int ans = 0; while (num) { num = num & 1 ? num - 1 : num >> 1; ++ans; } return ans; }};class Solution: def numberOfSteps(self, num: int) -> int: ans = 0 while num: if num & 1: num -= 1 else: num >>= 1 ans += 1 return ansVideo 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.