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.
- 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 <= 1000001 <= maximumBit <= 200 <= nums[i] < 2^maximumBit
Hints for Maximum XOR for Each Query
Hint 1
For a fixed XOR total
t, thekthat maximisest XOR kwithinmaximumBitbits ist XOR mask, wheremask = 2^maximumBit - 1.Hint 2
That gives
maskitself as the maximised value — the answer is thek, not the maximum.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
- Set
mask = 2^maximumBit - 1and computetotal, the XOR of all elements. - Sweep
ifrom the last index down to 0: recordtotal ^ mask, then XORnums[i]out oftotal. - 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 thekthat achieves it. - Sweeping forwards removes the wrong elements — the array shrinks from the back.
1 << 20is safe in every target language, but building the mask withMath.powavoids 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 outJava
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