Maximum XOR for Each Query

medium prefix xor bit manipulation array

Problem

Given a sorted array nums of n non-negative integers and an integer maximumBit, perform n queries. For query i: pick k < 2^maximumBit that maximizes nums[0] XOR … XOR nums[last] XOR k over the current array, record that k in answer[i], then drop the last element. Return answer.

Because XOR with a free k can flip any bits below maximumBit, the maximum is always all-ones 2^maximumBit − 1, and the best k is the current prefix XOR flipped against that mask.

Inputnums = [0,1,1,3], maximumBit = 2

Output[0,3,2,3]

XOR of [0,1,1,3] is 3; with mask 3, k = 3 ^ 3 = 0. Remove 3 → XOR of [0,1,1] is 0; k = 0 ^ 3 = 3, and so on.

nums (comma-separated)

maximumBit (1..20)

def getMaximumXor(nums, maximumBit):
    mask = (1 << maximumBit) - 1       # all-ones target 2^bit - 1
    total = 0
    for v in nums:                     # XOR of the whole array
        total ^= v
    answer = []
    for v in reversed(nums):           # query order: drop last each time
        answer.append(total ^ mask)    # k that flips prefix XOR to all ones
        total ^= v                     # remove last element for next query
    return answer

function getMaximumXor(nums, maximumBit) {
  const mask = (1 << maximumBit) - 1;     // all-ones target 2^bit - 1
  let total = 0;
  for (const v of nums) total ^= v;       // XOR of the whole array
  const answer = [];
  for (let i = nums.length - 1; i >= 0; i--) {
    answer.push(total ^ mask);            // k that flips prefix XOR to all ones
    total ^= nums[i];                     // remove last element for next query
  }
  return answer;
}

int[] getMaximumXor(int[] nums, int maximumBit) {
    int mask = (1 << maximumBit) - 1;        // all-ones target 2^bit - 1
    int total = 0;
    for (int v : nums) total ^= v;          // XOR of the whole array
    int n = nums.length;
    int[] answer = new int[n];
    for (int i = 0; i < n; i++) {
        answer[i] = total ^ mask;           // k flips prefix XOR to all ones
        total ^= nums[n - 1 - i];           // remove last element
    }
    return answer;
}

vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
    int mask = (1 << maximumBit) - 1;        // all-ones target 2^bit - 1
    int total = 0;
    for (int v : nums) total ^= v;          // XOR of the whole array
    int n = nums.size();
    vector<int> answer(n);
    for (int i = 0; i < n; i++) {
        answer[i] = total ^ mask;           // k flips prefix XOR to all ones
        total ^= nums[n - 1 - i];           // remove last element
    }
    return answer;
}

Explanation

The key insight is that k is free to be any value below 2^maximumBit, so XORing with k can flip any subset of the lowest maximumBit bits. The largest value those bits can form is all-ones, the mask 2^maximumBit − 1.

If the XOR of the current array is total, then to reach the mask we need total XOR k = mask, which means k = total XOR mask. Since every nums[i] < 2^maximumBit, total never has bits above the mask, so this k is always a valid answer below 2^maximumBit.

Each query removes the last element, which shrinks the array to a prefix. The XOR of a prefix is just the running XOR with the dropped elements peeled off, so this is a prefix-XOR problem: compute the full XOR once, then walk backwards, peeling one element off total after recording each answer.

That gives all n answers in a single backward pass — no recomputation per query.

Example: nums = [0,1,1,3], maximumBit = 2 so mask = 3. Full XOR is 3, answer 3^3 = 0. Peel 3 → XOR 0, answer 0^3 = 3. Peel 1 → XOR 1, answer 1^3 = 2. Peel 1 → XOR 0, answer 0^3 = 3. Result [0,3,2,3].

Time: O(n) Space: O(n) for the output (O(1) extra)