Maximum XOR for Each Query

Medium
736.

Maximum XOR for Each Query

Maximum XOR for Each Query is a medium coding problem on arrays, bit manipulation and prefix sum, asked in Amazon, Google and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} maximumBit
 * @return {number[]}
 */
var getMaximumXor = function(nums, maximumBit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum XOR for Each Query — Solution in Python, Java & C++

Maximum XOR for Each Query solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum XOR for Each Query is a medium coding problem on arrays, bit manipulation and prefix sum, asked in Amazon, Google and Flipkart interviews.

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

Hints for Maximum XOR for Each Query

  1. Hint 1

    For a fixed XOR total t, the k that maximises t XOR k within maximumBit bits is t XOR mask, where mask = 2^maximumBit - 1.

  2. Hint 2

    That gives mask itself as the maximised value — the answer is the k, not the maximum.

  3. Hint 3

    Removing the last element just XORs it out of the running total, so one backward sweep suffices.

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

  1. Set mask = 2^maximumBit - 1 and compute total, the XOR of all elements.
  2. Sweep i from the last index down to 0: record total ^ mask, then XOR nums[i] out of total.
  3. 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

Java

public static int[] getMaximumXor(int[] nums, int maximumBit) {
    int mask = (1 << maximumBit) - 1;
    int total = 0;
    for (int x : nums) total ^= x;
    int n = nums.length;
    int[] out = new int[n];
    for (int i = 0; i < n; i++) {
        out[i] = total ^ mask;
        total ^= nums[n - 1 - i];
    }
    return out;
}

C++

vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
    int mask = (1 << maximumBit) - 1;
    int total = 0;
    for (int x : nums) total ^= x;
    vector<int> out;
    for (int i = (int) nums.size() - 1; i >= 0; i--) {
        out.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation