Maximum XOR for Each Query — Medium Problem & Solution

Every element of nums is smaller than 2^maximumBit. Repeat until the array is empty: choose the non-negative k < 2^maximumBit that maximises the XOR of k…

Difficulty: Medium
Topics: Arrays, Bit Manipulation, Prefix Sum
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Every element of nums is smaller than 2^maximumBit. Repeat until the array is empty: choose the non-negative k < 2^maximumBit that maximises the XOR of k with all remaining elements, record k, then remove the last element.

Return the recorded values in order.

Example 1

Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation: The array XORs to 3, so the first k is 3 XOR 3 = 0.

Example 2

Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]

Example 3

Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]

Constraints

1 <= nums.length <= 100000
1 <= maximumBit <= 20
0 <= nums[i] < 2^maximumBit

How to solve Maximum XOR for Each Query

Flipping every bit of the running XOR gives the all-ones value, which is the largest possible within maximumBit bits. So the answer for a given state is total XOR mask, and removals are handled by XOR-ing the departing element out.

Approach

Set mask = 2^maximumBit - 1 and compute total, the XOR of all elements.
Sweep i from the last index down to 0: record total ^ mask, then XOR nums[i] out of total.
Return the recorded values in the order they were produced.

Why it works

t ^ k is maximised over k < 2^b by choosing k so the result is all ones, which forces k = t ^ mask — and that k is in range because t is. Removing the last element is undone by XOR-ing it again, since XOR is its own inverse.

Complexity

Time — O(n)
Space — O(n) for the output

Pitfalls

Returning the maximised XOR value (always mask) instead of the k that achieves it.
Sweeping forwards removes the wrong elements — the array shrinks from the back.
1 << 20 is safe in every target language, but building the mask with Math.pow avoids any doubt in JavaScript.

Reference solution

Python

from typing import List

def getMaximumXor(nums: List[int], maximumBit: int) -> List[int]:
    mask = (1 << maximumBit) - 1
    total = 0
    for x in nums:
        total ^= x
    out = []
    for i in range(len(nums) - 1, -1, -1):
        out.append(total ^ mask)
        total ^= nums[i]
    return out

JavaScript

var getMaximumXor = function(nums, maximumBit) {
    var mask = Math.pow(2, maximumBit) - 1;
    var total = 0;
    for (var i = 0; i < nums.length; i++) total ^= nums[i];
    var out = [];
    for (var j = nums.length - 1; j >= 0; j--) {
        out.push(total ^ mask);
        total ^= nums[j];
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue