2571. Minimum Operations to Reduce an Integer to 0
Asked at Microsoft, Salesforce, Uber
Difficulty
Medium
Time
O(log n)
Space
O(1)
Pattern
Dynamic Programming
Companies
3
Problem
You are given a positive integer n. In one operation you may add or subtract a power of 2 (that is, 1, 2, 4, 8, ...) from n. You may use any power of 2 each time, and you may use the same one more than once.
Return the minimum number of operations needed to turn n into 0.
The trick is that adding is allowed, not just subtracting. Sometimes going up first is cheaper, because a single add can create a carry that clears a whole block of 1-bits at once.
One operation changes n by a power of 2
Constraints
- ●
1 <= n <= 10^5
Examples
n = 393n = 543Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Microsoft | Medium | View all Microsoft questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Brute force: use BFS or DP where the state is the current value of n. From each state, you can go to n-1 or n+1. Find the shortest path to 0. This works but is inefficient for large n.
Key insight: think in binary. Every bit that is 1 contributes to the cost. The optimal strategy is to flip bits from the lowest set bit upward. When you have a run of consecutive 1s, it is cheaper to add 1 (causing a carry that flips the entire run) than to subtract 1 individually.
Greedy approach: look at the binary representation of n. Count the number of 1-bits. When you encounter consecutive 1s, adding 1 is better (costs 1 operation but flips multiple bits via carry). When you encounter isolated 1s, subtracting 1 is better.
The algorithm: while n > 0, if n is odd (LSB is 1), check the next bit. If the next bit is also 1, add 1 (flip the run via carry). If the next bit is 0, subtract 1 (flip the isolated 1). If n is even, shift right (divide by 2). Count operations.
Time: O(log n) — we examine each bit at most once. Space: O(1). The greedy bit manipulation approach is far more efficient than BFS or DP.
Edge cases: n=0 (0 operations), n=1 (1 operation: subtract 1), n=power of 2 (just subtract n times, or use bit tricks for fewer operations).
Optimal Approach
Greedy bit manipulation:
- Initialize
ops = 0. - While n > 0:
- If n is odd (LSB is 1): check if the next bit is also 1 (n & 2). If yes, add 1 (flips the run of 1s via carry). If no (isolated 1), subtract 1.
- If n is even (LSB is 0): shift right (divide by 2).
- Increment ops.
- Return ops.
Walkthrough: n = 6 (110)
- n=6 (110): even, shift right -> n=3 (11), ops=0
- n=3 (11): odd, next bit is 1, add 1 -> n=4 (100), ops=1
- n=4 (100): even, shift right -> n=2 (10), ops=1
- n=2 (10): even, shift right -> n=1 (1), ops=1
- n=1 (1): odd, next bit is 0, subtract 1 -> n=0, ops=2
Result: 2 operations.
Time: O(log n). Space: O(1).
Greedy on the low bits
What Trips People Up in Real Interviews
Misunderstanding the problem as allowing arbitrary additions/subtractions. The operations are strictly +1 or -1. The bit manipulation trick works because adding 1 to a number with consecutive 1-bits causes a carry that flips multiple bits at once.
Not checking the second bit when the first bit is 1. If n & 3 == 3 (two consecutive 1s), adding 1 flips both. If n & 3 == 1 (isolated 1), subtracting 1 is better. Forgetting this check makes the algorithm suboptimal.
Trying a DP approach with a hash set of visited states. This works but is O(n) time and space. The bit manipulation approach is O(log n) and should be presented first.
Confusing this with a problem where you can subtract powers of 2. Here the only operations are +1 and -1. The bit trick exploits the fact that adding 1 to consecutive 1-bits causes a carry chain.
Not handling n=0. The while loop condition n > 0 handles it correctly (0 iterations, return 0), but some implementations have an off-by-one or infinite loop when n=0.
Solution Code
O(log n) timedef minOperations(n):
ops = 0
while n > 0:
if n & 1:
if n & 2:
n += 1
else:
n -= 1
ops += 1
else:
n >>= 1
return opsFrequently Asked Questions
What is the Minimum Operations to Reduce an Integer to 0 problem?
You are given a positive integer n. In one operation, you can either subtract 1 from n or add 1 to n. Return the minimum number of operations required to make n equal to 0.
How do you solve Minimum Operations to Reduce an Integer to 0?
The optimal approach runs in O(log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Minimum Operations to Reduce an Integer to 0?
Minimum Operations to Reduce an Integer to 0 is asked at Microsoft, Salesforce, Uber. It is a medium difficulty problem.
What are common mistakes on Minimum Operations to Reduce an Integer to 0?
- Misunderstanding the problem as allowing arbitrary additions/subtractions. The operations are strictly +1 or -1. The bit manipulation trick works because adding 1 to a number with consecutive 1-bits causes a carry that flips multiple bits at once.
- Not checking the second bit when the first bit is 1. If n & 3 == 3 (two consecutive 1s), adding 1 flips both. If n & 3 == 1 (isolated 1), subtracting 1 is better. Forgetting this check makes the algorithm suboptimal.
- Trying a DP approach with a hash set of visited states. This works but is `O(n)` time and space. The bit manipulation approach is `O(log n)` and should be presented first.
- Confusing this with a problem where you can subtract powers of 2. Here the only operations are +1 and -1. The bit trick exploits the fact that adding 1 to consecutive 1-bits causes a carry chain.
- Not handling n=0. The while loop condition `n > 0` handles it correctly (0 iterations, return 0), but some implementations have an off-by-one or infinite loop when n=0.