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
- For a fixed prefix value
p, the XORp ^ kis maximised by choosingkto flip every bit ofpwithin the firstmaximumBitpositions. - That value of
kis simplyp ^ ((1 << maximumBit) - 1), and it is always below2^maximumBit. - Compute the total XOR once; it is the prefix for the first query.
- 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
kbit by bit greedily: the closed formprefix ^ fullgives the optimum in one step. - Using
1 << maximumBitas the mask: it must be(1 << maximumBit) - 1, so thatkstays 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.