Max XOR Each Query LeetCode 1829 Guide

LeetCode 1829 — Maximum XOR for Each Query — gives you a sorted integer array nums and a positive integer maximumBit k. You must answer n queries, where query i asks: what value x in [0, 2^k - 1] maximizes the XOR of x with all elements currently in nums? After answering each query, the last element of nums is removed.

The result array ans has the same length as nums. ans[0] corresponds to using all elements, ans[1] corresponds to all elements except the last one, and so on. Because k is bounded, x is a k-bit non-negative integer — choosing x optimally always requires inspecting every bit of the running XOR in the lower k positions.

This problem sits at the intersection of prefix XOR and bitwise complement techniques. The key insight is that XOR of all current elements is easy to maintain incrementally, and maximizing XOR with a fixed range [0, 2^k - 1] has a clean closed-form answer.

XOR all elements of the current array gives a value called xorAll. To maximize xorAll XOR x where x can be any k-bit number, you want every bit of x to be the opposite of the corresponding bit of xorAll in the lower k positions. This is precisely the bitwise complement of xorAll restricted to k bits.

The k-bit complement of xorAll is computed as xorAll XOR mask, where mask = (1 << k) - 1. The mask has exactly k ones in its lower bits, so XOR with the mask flips all k lower bits of xorAll and leaves higher bits unaffected. This one operation gives the optimal x for any query in O(1).

Because nums[i] < 2^k by constraint, the XOR of all elements also fits in k bits. The higher bits of xorAll are always zero, so XOR with mask also zeroes out the higher bits of the result, keeping x in the valid range [0, 2^k - 1].

First compute xorAll as the XOR of all elements in nums. Then build the mask as (1 << k) - 1. The first answer is xorAll XOR mask. Then iterate from the last element of nums backwards: XOR it out of xorAll and compute the next answer as xorAll XOR mask. This fills the answer array from index 0 to n-1 in one forward pass.

The entire algorithm is O(n) time and O(n) space (for the result). The initial XOR computation is O(n), and each of the n query steps is O(1). No sorting or additional data structures are required beyond the result array.

Because we process elements from back to front, xorAll naturally shrinks by removing nums[n-1], then nums[n-2], and so on — matching exactly the order in which the problem removes elements.

The problem specifies that each query removes the last element of the remaining array. So query 0 uses all n elements, query 1 uses the first n-1 elements (removing nums[n-1]), query 2 uses the first n-2 elements, and so on. The removal proceeds from right to left in the original array.

Processing from the back perfectly matches this removal order. Starting with the full XOR, we XOR out nums[n-1] to get the prefix XOR for query 1, then XOR out nums[n-2] for query 2, etc. Each XOR-out is O(1) because XOR is its own inverse: a XOR a = 0.

Alternatively, one could precompute prefix XOR values from left to right and index them directly. Both approaches are O(n), but the backwards loop avoids building the prefix array entirely and is a single clean loop.

Let nums = [0, 1, 1, 3] and k = 2. First compute mask = (1 << 2) - 1 = 3 (binary 11). Compute xorAll = 0 XOR 1 XOR 1 XOR 3 = 3 (binary 11). Query 0 (all elements): ans[0] = 3 XOR 3 = 0. Remove nums[3] = 3: xorAll = 3 XOR 3 = 0. Query 1: ans[1] = 0 XOR 3 = 3.

Remove nums[2] = 1: xorAll = 0 XOR 1 = 1. Query 2: ans[2] = 1 XOR 3 = 2. Remove nums[1] = 1: xorAll = 1 XOR 1 = 0. Query 3: ans[3] = 0 XOR 3 = 3. Final result: [0, 3, 2, 3].

Verify query 0: XOR(0,1,1,3) = 3; best x = 0 since 3 XOR 0 = 3, but 3 XOR 0 = 3 and 3 XOR 3 = 0 — wait, we want to maximize: ans[0]=0 means x=0 gives 3 XOR 0=3, while x=3 gives 3 XOR 3=0. So best x=0 giving XOR=3. Correct.

Python: from functools import reduce; from operator import xor; def getMaximumXor(nums, maximumBit): mask = (1 << maximumBit) - 1; xorAll = reduce(xor, nums); ans = []; [ans.append(xorAll ^ mask) or setattr(__builtins__, "_", xorAll := xorAll ^ nums[i]) for i in range(len(nums)-1, -1, -1)]. Cleaner version: compute xorAll, then loop from back appending xorAll^mask and XORing out each element. O(n) time, O(n) space.

Java: public int[] getMaximumXor(int[] nums, int maximumBit) { int n = nums.length; int mask = (1 << maximumBit) - 1; int xorAll = 0; for (int x : nums) xorAll ^= x; int[] ans = new int[n]; for (int i = 0; i < n; i++) { ans[i] = xorAll ^ mask; xorAll ^= nums[n - 1 - i]; } return ans; }. Forward loop from i=0 to n-1 fills ans in order, XORing out the last element each step.

Both implementations avoid nested loops. The Python reduce initializes xorAll in one line; the Java version uses an explicit loop for clarity. Space is O(n) for the output array only — no auxiliary data structure is needed.

LeetCode 1829 belongs to the prefix XOR family. Single Number (LeetCode 136) is the classic XOR application — XOR all elements to isolate the unique value, since pairs cancel. The same property (a XOR a = 0) powers both Single Number and the incremental removal in 1829.

Bitwise AND of Numbers in a Range (LeetCode 201) is the AND counterpart: it finds common prefix bits of a range. Largest Combination with Bitwise AND (LeetCode 2275) counts elements sharing a common bit. Both problems require understanding how bitwise operations interact with sets of numbers, just as 1829 does.

Other close relatives include XOR Queries of a Subarray (LeetCode 1310), which uses prefix XOR to answer range queries in O(1) each, and Find the XOR of Numbers Which Appear Twice (LeetCode 2433). Mastering prefix XOR and bitwise complement as tools unlocks all of these efficiently.