Maximum XOR for Each Query: Prefix XOR Pattern

LeetCode Maximum XOR for Each Query (Problem 1829) asks: given a sorted array nums and an integer maximumBit, answer n queries. For the ith query, find the value k (where 0 <= k < 2^maximumBit) that maximizes nums[0] XOR nums[1] XOR ... XOR nums[n-1-i] XOR k. After each query, remove the last element from the current array.

For example, with nums = [0, 1, 1, 3] and maximumBit = 2, the answer is [0, 3, 2, 3]. Each query picks the k that maximizes the XOR of the remaining elements with k.

Why this problem matters

This problem combines two fundamental bit manipulation ideas: prefix XOR and bit masking. In interviews, XOR-based problems show up often because they test whether you understand how XOR interacts with itself and with masks. The "process in reverse" pattern also appears in problems where you need to undo operations efficiently.

The key insight: XOR with a mask

The XOR of all elements in the array gives you a value called prefix_xor. To maximize prefix_xor XOR k, you want k to flip every bit of prefix_xor within the maximumBit range. Why? Because XOR produces a 1 whenever the two bits differ. If you flip every bit in prefix_xor, the result is all 1s in those bit positions, which is the largest possible value.

The mask that covers all maximumBit bits is (1 << maximumBit) - 1. For maximumBit = 2, the mask is 11 in binary (decimal 3). Then k = prefix_xor XOR mask.

For each subsequent query, you remove the last element from the array. Instead of recomputing the XOR from scratch, you XOR out the removed element: prefix_xor ^= nums[i]. This works because XOR is its own inverse. XOR-ing a value twice cancels it out.

Processing from the end of the array means you handle query 0 first (with all elements), then query 1 (after removing the last element), and so on.

Python solution

def get_maximum_xor(nums: list[int], maximum_bit: int) -> list[int]:
    mask = (1 << maximum_bit) - 1
    xor_all = 0
    for num in nums:
        xor_all ^= num

    result = []
    for i in range(len(nums) - 1, -1, -1):
        result.append(xor_all ^ mask)
        xor_all ^= nums[i]

    return result

Detailed explanation

The algorithm works in two phases.

Phase 1: Compute the total XOR. Walk through the entire array and XOR every element together. This gives you the cumulative XOR of all n elements. The cost is O(n).

Phase 2: Process queries in reverse. For each query, the answer is xor_all ^ mask. The mask has all bits set within the maximumBit range, so XOR-ing with it flips every bit, producing the maximum possible XOR result. After recording the answer, remove the last element by XOR-ing it out of xor_all. This "undoes" that element from the prefix.

Why does XOR-ing with the mask give the maximum? The XOR of prefix_xor and k can have at most maximumBit bits. To make all those bits 1, you need k to be the bitwise complement of prefix_xor within that bit range. That complement is exactly prefix_xor ^ mask.

Walkthrough

Let's trace through nums = [0, 1, 1, 3] with maximumBit = 2.

The algorithm processes four queries, each time computing xor_all ^ mask and then removing the last remaining element. The final result is [0, 3, 2, 3].

Complexity analysis

The first pass computes the total XOR in O(n). The second pass iterates backward through the array, doing constant work per element. The result array holds n values.

Building blocks

This problem decomposes into two reusable building blocks that CodeBricks drills independently:

Prefix XOR

The cumulative XOR of array elements is analogous to a prefix sum, but with XOR instead of addition. Just as prefix sums let you compute range sums in O(1), prefix XOR lets you compute the XOR of any subarray efficiently. The key property is that XOR is both associative and its own inverse: a ^ a = 0.

xor_all = 0
for num in nums:
    xor_all ^= num

Bit masking for complement

A mask of all 1s within a given bit width lets you compute the bitwise complement of any value within that range. XOR-ing a value with the mask flips every bit. This pattern appears whenever you need to find the "opposite" bit pattern or maximize an XOR expression.

mask = (1 << maximum_bit) - 1
complement = value ^ mask

Edge cases

All elements are zero. When every element is 0, xor_all is 0, and every query returns mask. The mask itself is the maximum value representable in maximumBit bits.

Single element. With one element, there is only one query. The answer is nums[0] ^ mask. After that, the array is empty.

maximumBit is 1. The mask is 1, so k is always 0 or 1. Each query returns the complement of the least significant bit of the current XOR.

All bits already set. If the XOR of all elements equals the mask (all bits within range are 1), then k = 0 for the first query. The maximum XOR is achieved without flipping any bits.

From understanding to recall

The prefix XOR plus mask approach is elegant once you see it. But recognizing the pattern under pressure requires practice. You need to instinctively connect "maximize XOR" with "XOR the complement" and "process in reverse" with "XOR out removed elements."

Spaced repetition builds that recall. You write the two-phase loop from memory today, again in a few days, then a week later. Each repetition strengthens the connection between the problem shape and the technique. When you see a problem that asks to maximize an XOR expression, the mask-complement idea will surface immediately.

Related posts

• Single Number - Foundational XOR cancellation pattern
• Counting Bits - Bit-level reasoning and patterns
• Bitwise AND of Numbers Range - Bitwise operations on ranges