⚡Flashcard Drill➔
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

  1. 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.
  2. 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) ^ ....
  3. Intuitively, each move flips the highest legal bit, mirroring how the Gray code sequence changes one bit at a time.
  4. Implement with a loop: res ^= n; n >>= 1 until n becomes 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^30 states 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 i to 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems