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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n) for the prefix array.
| 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) |
L7. Maximum XOR With an Element From Array | Queries | C++ | Java • take U forward • 62,923 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