Maximum XOR for Each Query
MedPrompt
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:
- Find a non-negative integer
k < 2maximumBitsuch thatnums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR kis maximized.kis the answer to theithquery. - Remove the last element from the current array
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. For each of the n queries, we first calculate the XOR sum of all elements currently in the array. Then, we determine the value of k that would maximize the total XOR sum. This k is stored, and finally, the last element of the array is removed to set up for the next query. This entire process is repeated n times.
Algorithm
-
- Initialize an
answerarray of sizen.
- Initialize an
-
- Create a mutable
Listfrom the inputnumsarray to facilitate element removal.
- Create a mutable
-
- Calculate
max_val = (1 << maximumBit) - 1. This represents the number with allmaximumBitbits set to 1, which is the target for our maximization.
- Calculate
-
- Loop
ntimes, fromi = 0ton-1, to simulate each query:
- a. Initialize a variable
current_xor = 0. - b. Iterate through all elements of the current list and compute their bitwise XOR sum, storing it in
current_xor. - c. The value of
kthat maximizes the expression isk = current_xor ^ max_val. - d. Store this
kin the results:answer[i] = k. - e. Remove the last element from the list to prepare for the next query.
- Loop
-
- Return the
answerarray.
- Return the
Walkthrough
The core idea is to find a non-negative integer k < 2^maximumBit that maximizes the expression (nums[0] XOR ... XOR nums[m-1]) XOR k. The maximum possible value for an expression constrained to maximumBit bits is 2^maximumBit - 1. Let's call this max_val. To achieve this maximum result, we need to have (XOR of current nums) XOR k = max_val. By applying XOR properties, we can solve for k: k = max_val XOR (XOR of current nums).
The brute-force algorithm implements this logic straightforwardly. It iterates n times, and in each iteration, it re-calculates the XOR sum of the shrinking array, computes k, and then removes the last element. Using a dynamic data structure like an ArrayList in Java makes the removal of the last element convenient.
import java.util.ArrayList;import java.util.List; class Solution { public int[] getMaximumXor(int[] nums, int maximumBit) { int n = nums.length; int[] answer = new int[n]; List<Integer> currentNums = new ArrayList<>(); for (int num : nums) { currentNums.add(num); } int maxVal = (1 << maximumBit) - 1; for (int i = 0; i < n; i++) { // 1. Calculate current XOR sum int currentXor = 0; for (int num : currentNums) { currentXor ^= num; } // 2. Find k int k = currentXor ^ maxVal; answer[i] = k; // 3. Remove the last element if (!currentNums.isEmpty()) { currentNums.remove(currentNums.size() - 1); } } return answer; }}Complexity
Time
O(n^2) - The outer loop runs `n` times for the `n` queries. The inner loop, which calculates the XOR sum, runs `n`, `n-1`, `n-2`, ..., `1` times. The total number of XOR operations is the sum of this arithmetic series, which is `n * (n+1) / 2`, resulting in a quadratic time complexity.
Space
O(n) - We use an `ArrayList` to store a copy of the numbers, which takes O(n) space. The `answer` array also requires O(n) space.
Trade-offs
Pros
It is simple to understand and implement as it directly translates the problem description into code.
It's a good starting point for understanding the problem mechanics before moving to more optimized solutions.
Cons
The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5), and this solution will likely result in a 'Time Limit Exceeded' error.
It performs a lot of redundant work by re-calculating the XOR sum from scratch in each of the n queries.
Solutions
Solution
public class Solution { public int[] GetMaximumXor(int[] nums, int maximumBit) { int xs = 0; foreach(int x in nums) { xs ^= x; } int n = nums.Length; int[] ans = new int[n]; for (int i = 0; i < n; ++i) { int x = nums[n - i - 1]; int k = 0; for (int j = maximumBit - 1; j >= 0; --j) { if ((xs >> j & 1) == 0) { k |= 1 << j; } } ans[i] = k; xs ^= x; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.