You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:
k < 2maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the ith query.nums.Return an array answer, where answer[i] is the answer to the ith query.
Example 1:
Input: nums = [0,1,1,3], maximumBit = 2 Output: [0,3,2,3] Explanation: The queries are answered as follows: 1st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3. 2nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3. 3rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3. 4th query: nums = [0], k = 3 since 0 XOR 3 = 3.
Example 2:
Input: nums = [2,3,4,7], maximumBit = 3 Output: [5,2,6,5] Explanation: The queries are answered as follows: 1st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7. 2nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7. 3rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7. 4th query: nums = [2], k = 5 since 2 XOR 5 = 7.
Example 3:
Input: nums = [0,1,2,2,5,7], maximumBit = 3 Output: [4,3,6,4,6,7]
Constraints:
nums.length == n1 <= n <= 1051 <= maximumBit <= 200 <= nums[i] < 2maximumBitnums is sorted in ascending order.Problem Overview: You receive an integer array nums and a value maximumBit. For each query, you consider the prefix of the array and choose an integer k (0 ≤ k < 2maximumBit) that maximizes prefixXor ^ k. After each query, the last element of the array is removed. The task is to return the optimal k for every query.
Approach 1: Precompute and Use XOR Properties (Time: O(n), Space: O(n))
This approach relies on a key property of bit manipulation: the value that maximizes x ^ k is the bitwise complement of x within the allowed bit range. First compute the prefix XOR of the entire array using a prefix XOR technique. Let mask = (1 << maximumBit) - 1, which represents the largest number allowed for k. For each query, the best value of k is simply prefixXor ^ mask. After producing the result, remove the last element logically by XOR-ing it out of the running prefix. This avoids recomputing XOR values repeatedly and processes the queries in reverse order.
The strength of this method is its simplicity. You compute the total XOR once, then update it incrementally as the array shrinks. XOR operations are constant time, so the entire algorithm runs in linear time relative to the array size.
Approach 2: Calculate On-The-Fly with Prefix XOR Array (Time: O(n), Space: O(n))
This variation explicitly builds a prefix XOR array where prefix[i] stores the XOR of elements from index 0 to i. Each query corresponds to a prefix length that decreases over time. Instead of modifying a running XOR variable, you directly reference the appropriate prefix value. For the current prefix XOR value x, compute the optimal answer using the same mask trick: k = x ^ mask. Because XOR with the mask flips all bits within the allowed range, the result produces the maximum possible XOR value.
The main difference is clarity versus memory usage. Using a prefix array can make debugging easier because every prefix XOR is stored explicitly. However, it requires extra memory compared with maintaining a single running XOR.
Recommended for interviews: The expected solution uses XOR properties with a running prefix value and a bitmask. Interviewers want to see recognition that maximizing x ^ k means flipping every bit within the allowed range. Starting with the straightforward prefix XOR idea demonstrates understanding, while deriving the mask trick shows strong comfort with bitwise operations. The optimal implementation runs in O(n) time with O(1) auxiliary space.
In this approach, we compute the total XOR of the array and then, for each query, determine the best integer k to maximize the XOR. We leverage the fact that XOR of a number with itself is 0, and XOR with 0 is the number itself. The trick is to use the maximum number in the range [0, 2^maximumBit) as an XOR mask to get the maximum number at each step.
We'll precompute the total XOR of the given array. For each step, find k by XORing the current XOR value with the maximum possible number, which is `(2^maximumBit - 1)`. After each query, remove the last element and update the XOR till it becomes empty.
This implementation uses a function to calculate the maximum XOR for the queries. It first computes the total XOR of the entire array. For each element, it uses the bitmask maxNum to find the maximum k by XORing it with the current total XOR value. Then, it removes the last element's effect by XORing it again.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1) additional space beyond input and output arrays.
This approach calculates the XOR using prefix sums for XOR which allows direct computation of the desired XOR values for any subset by removing the influence of past elements efficiently. We combine this with the known max number XOR mask strategy to derive each query's answer.
First, we compute the prefix XOR array which gives cumulative XOR up to any index. By doing so, calculating new ranges becomes direct through array subtraction for the prefix array indices, because of the property (A XOR A = 0) property that cancels out all elements between boundaries.
This code uses a prefix XOR array that keeps track of all XOR values up to each index. The result for each query, which requests the maximum XOR when combinations incorporate fewer elements, is calculated based on these cumulative XOR values adjusted with the maximum potential XOR mask before appending results.
Time Complexity: O(n)
Space Complexity: O(n) for the prefix array.
First, we preprocess the XOR sum xs of the array nums, i.e., xs=nums[0] \oplus nums[1] \oplus cdots \oplus nums[n-1].
Next, we enumerate each element x in the array nums from back to front. The current XOR sum is xs. We need to find a number k such that the value of xs \oplus k is as large as possible, and k \lt 2^{maximumBit}.
That is to say, we start from the maximumBit - 1 bit of xs and enumerate to the lower bit. If a bit of xs is 0, then we set the corresponding bit of k to 1. Otherwise, we set the corresponding bit of k to 0. In this way, the final k is the answer to each query. Then, we update xs to xs \oplus x and continue to enumerate the next element.
The time complexity is O(n times m), where n and m are the values of the array nums and maximumBit respectively. Ignoring the space consumption of the answer, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
C#
Similar to Solution 1, we first preprocess the XOR sum xs of the array nums, i.e., xs=nums[0] \oplus nums[1] \oplus cdots \oplus nums[n-1].
Next, we calculate 2^{maximumBit} - 1, which is 2^{maximumBit} minus 1, denoted as mask. Then, we enumerate each element x in the array nums from back to front. The current XOR sum is xs, then k=xs \oplus mask is the answer to each query. Then, we update xs to xs \oplus x and continue to enumerate the next element.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
C#
| Approach | Complexity |
|---|---|
| Approach 1: Precompute and Use XOR Properties | Time Complexity: O(n), where n is the length of the array. |
| Approach 2: Calculate On-The-Fly with Prefix XOR Array | Time Complexity: O(n) |
| Bitwise Operation + Enumeration | — |
| Enumeration Optimization | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force XOR for Each Query | O(n^2) | O(1) | Useful only for understanding the problem constraints or validating small test cases |
| Precompute and Use XOR Properties | O(n) | O(1) | Best general solution; uses XOR mask trick and updates prefix XOR as elements are removed |
| Prefix XOR Array | O(n) | O(n) | When you want explicit prefix values for clarity or debugging |
Maximum XOR for Each Query | Simple Explanation | Leetcode 1829 | codestorywithMIK • codestorywithMIK • 9,107 views views
Watch 9 more video solutions →Practice Maximum XOR for Each Query with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor