Minimum One Bit Operations to Make Integers Zero
Hard · Bit Manipulation · Bit Manipulation · Recursion · Dynamic Programming · Memoization
Problem
You are given a non-negative integer n and must turn it into 0 with these two moves, used as often as you like:
- Flip the lowest bit (bit 0) of n.
- Flip bit i (for i >= 1) only when bit i - 1 is 1 and every bit below i - 1 is 0.
Return the minimum number of moves needed to reach 0.
Examples
Input: n = 2 Output: 3
10 → 11 (move 1) → 01 (move 2, bit 0 is 1) → 00 (move 1): three moves.
Input: n = 5 Output: 6
101 → 111 → 110 → 010 → 011 → 001 → 000: six moves, and no shorter legal sequence exists.
Input: n = 0 Output: 0
Already zero.
Constraints
- 0 <= n <= 10^9
Approaches
- Recurse on the highest bit — time O(log² n), space O(log n)
Follow-up
The moves trace the reflected Gray code, so this is the Gray-code decode. Shifting by 1, 2, 4, 8 and 16 decodes a 32-bit number in five XORs. The use cases run the code forwards (the state after k moves) and measure the distance between two states.
Related problems
Start free on Cariara · Coding problems · System design studio
