NeetCode #940LC-1611HardMath & Geometry
← Back to All Problems#940 · #1611 · Minimum One Bit Operations to Make Integers Zero(使整数变为 0 的最少操作次数)
📌 Problem Statement & Constraints
Given an integer
n, the allowed operations are: (1) flip the lowest bit (bit 0); (2) flip bit i for any i >= 1 provided bit i is 1 and all lower bits are 0. Return the minimum number of operations to turn n into 0. Constraints: 0 <= n <= 10^9.💡 Core Algorithmic Approaches
- This operation set is exactly the structure of the reflected Gray code, so the minimum number of moves equals the inverse Gray-code value of
n. - The forward Gray code is
n ^ (n >> 1); the inverse (the answer here) is the XOR of all right-shifts:n ^ (n >> 1) ^ (n >> 2) ^ .... - Intuitively, each move flips the highest legal bit, mirroring how the Gray code sequence changes one bit at a time.
- Implement with a loop:
res ^= n; n >>= 1untilnbecomes 0.
💻 Benchmark Python3 Implementation
class Solution:
def minimumOneBitOperations(self, n: int) -> int:
res = 0
while n:
res ^= n # accumulate n ^ (n >> 1) ^ (n >> 2) ^ ...
n >>= 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log n): one iteration per bit.
💾 Space Complexity
O(1): constant state.
⚠️ Interview Pitfalls & Follow-ups
- BFS over the state space:
2^30states are far too many. - Using
n ^ (n >> 1)(the forward Gray code): that is the opposite direction; the answer needs the XOR of all right-shifts. - Misreading operation (2): it requires bit
ito be 1 and every lower bit to be 0. - Recursing without a base case:
f(0) = 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.