⚡Flashcard Drill➔
NeetCode #868LC-1829MediumBit Manipulation
← Back to All Problems

#868 · #1829 · Maximum XOR for Each Query(每个查询的最大异或值)

📌 Problem Statement & Constraints

You are given a sorted array nums of n non-negative integers and an integer maximumBit. Perform n queries: in the i-th query, take the XOR of the first n - i elements and choose the largest k < 2^maximumBit that maximises the XOR with that prefix. Return the answers in order. Constraints: 1 <= nums.length <= 10^5, 1 <= maximumBit <= 20, 0 <= nums[i] < 2^maximumBit.

💡 Core Algorithmic Approaches

  1. For a fixed prefix value p, the XOR p ^ k is maximised by choosing k to flip every bit of p within the first maximumBit positions.
  2. That value of k is simply p ^ ((1 << maximumBit) - 1), and it is always below 2^maximumBit.
  3. Compute the total XOR once; it is the prefix for the first query.
  4. Each later query removes the last element of the prefix, which is done by XOR-ing it out since XOR is self-inverse.

💻 Benchmark Python3 Implementation

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        full = (1 << maximumBit) - 1    # all ones within maximumBit
        prefix = 0
        for x in nums:
            prefix ^= x
        res = []
        for i in range(len(nums)):
            res.append(prefix ^ full)   # flip every bit of the prefix
            prefix ^= nums[len(nums) - 1 - i]   # drop the last element
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to build the total XOR and one step per query.
💾 Space Complexity
O(1) beyond the output.

⚠️ Interview Pitfalls & Follow-ups

  • Choosing k bit by bit greedily: the closed form prefix ^ full gives the optimum in one step.
  • Using 1 << maximumBit as the mask: it must be (1 << maximumBit) - 1, so that k stays strictly below the limit.
  • Removing the wrong element: the prefix shrinks from the back, so XOR out nums[n - 1 - i].
  • Recomputing the prefix for every query: that is O(n^2); XOR-ing out the last element keeps it linear.
⚡
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 Bit Manipulation Problems