Minimum One Bit Operations to Make Integers Zero — Solution
Minimum One Bit Operations to Make Integers Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum One Bit Operations to Make Integers Zero is a hard coding problem on dynamic programming, math and bit manipulation, asked in Amazon, Google and Apple interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Bit Manipulation
- Asked at: Amazon, Google, Apple
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two operations transform a binary number:
- flip the rightmost bit (bit 0);
- flip bit
i + 1only if bitiis1and bitsi - 1 … 0are all0.
Return the minimum number of operations that turns n into 0.
Example 1
Input: n = 3
Output: 2
Explanation: 11 → 01 → 00.
Example 2
Input: n = 6
Output: 4
Explanation: 110 → 010 → 011 → 001 → 000.
Example 3
Input: n = 0
Output: 0
Constraints
0 <= n <= 1000000000
Hints for Minimum One Bit Operations to Make Integers Zero
Hint 1
The reachable states form a Gray-code ordering — each operation moves to an adjacent code word.
Hint 2
So the answer is the position of
nin the standard reflected Gray code.Hint 3
Converting a Gray code back to its index is the running XOR of the value's successive right shifts.
How to solve Minimum One Bit Operations to Make Integers Zero
The two operations are exactly the moves of the standard reflected binary (Gray) code: from a value you may step to the code word before or after it. So the minimum number of operations to reach 0 is the index of n in that code, and the Gray-to-binary conversion computes it directly.
Approach
- Start with
ans = 0. - While
n > 0, XORnintoansand shiftnright by one. - Return
ans.
Why it works
The Gray code of an index i is i ^ (i >> 1), and the inverse is i = g ^ (g >> 1) ^ (g >> 2) ^ … — precisely the running XOR of shifts. Since the operations move one step along the code, the distance from n to the code word 0 is its index.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
- A breadth-first search over states is exponential and cannot reach
10^9. - The recursive formula
f(n) = 2^k - f(n - 2^(k-1))… is equivalent but far easier to get wrong than the XOR-of-shifts form. - Use an unsigned or arithmetic shift, not a sign-propagating one;
nis non-negative so either works here.
Reference solution
Python
def minimumOneBitOperations(n: int) -> int:
ans = 0
while n > 0:
ans ^= n
n >>= 1
return ansJava
public static int minimumOneBitOperations(int n) {
int ans = 0;
while (n > 0) {
ans ^= n;
n >>>= 1;
}
return ans;
}C++
int minimumOneBitOperations(int n) {
int ans = 0;
unsigned int v = (unsigned int) n;
while (v > 0) {
ans ^= (int) v;
v >>= 1;
}
return ans;
}JavaScript
var minimumOneBitOperations = function(n) {
var ans = 0, v = n;
while (v > 0) {
ans ^= v;
v = Math.floor(v / 2);
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Bit Manipulation