Minimum One Bit Operations to Make Integers Zero
Problem
Transform an integer n into 0 using two operations, any number of times: (1) flip the rightmost (0th) bit; (2) flip the i-th bit only if bit (i−1) is 1 and bits (i−2)…0 are all 0. Return the minimum number of operations needed to reach 0.
n = 32n = 64def minimumOneBitOperations(n):
ans = 0
while n:
ans ^= n
n >>= 1
return ansfunction minimumOneBitOperations(n) {
let ans = 0;
while (n) {
ans ^= n;
n >>= 1;
}
return ans;
}int minimumOneBitOperations(int n) {
int ans = 0;
while (n != 0) {
ans ^= n;
n >>>= 1;
}
return ans;
}int minimumOneBitOperations(int n) {
int ans = 0;
while (n != 0) {
ans ^= n;
n >>= 1;
}
return ans;
}Explanation
The two allowed operations are exactly the moves that walk you one step along the standard reflected Gray code sequence. In that sequence, consecutive numbers differ in a single bit, and those single-bit flips are precisely operation 1 (the rightmost bit) and operation 2 (a higher bit guarded by a 1 then zeros). So the minimum number of operations to bring n down to 0 equals the position (index) of n in the Gray code sequence.
Recovering that index is the classic Gray-to-binary conversion. If g is a Gray code, its binary index b satisfies b = g XOR (g>>1) XOR (g>>2) XOR … — you XOR together every right-shifted copy of g until it becomes zero.
The loop does exactly this XOR fold: start with ans = 0, then repeatedly ans ^= n and shift n right by one. Each iteration mixes in one more shifted copy. When n reaches 0 the fold is complete and ans is the answer.
Why this is minimal: every Gray-code step changes the index by exactly 1, and the operations are reversible, so reaching 0 from index k can never take fewer than k moves — and the Gray walk achieves exactly k.
For n = 9 (binary 1001) the fold gives 1001 ⊕ 0100 ⊕ 0010 ⊕ 0001 = 1110 = 14, so 14 operations are required.
The loop runs once per bit of n, giving O(log n) time and O(1) extra space — no DP table or recursion needed.