1829. Maximum XOR for Each Query
SourceBiweekly Contest 50 Q3DifficultyMediumRating1523
Description
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.
Solutions
Solution 1: Bitwise Operation + Enumeration
Thinking
Each query asks for a \(k<2^{\textit{maximumBit}}\) maximizing the XOR with the current prefix XOR, then drops the last element. Recomputing the XOR from scratch is \(O(n^2)\). With \(n\le 10^5\) this will not pass.
Precompute the XOR \(xs\) of the whole array. When deleting from the back, \(k\) should flip every \(0\)-bit of \(xs\) inside the allowed width. Build \(k\) bit by bit, then fold the removed value out of \(xs\).
First, we preprocess the XOR sum \(xs\) of the array \(\textit{nums}\), i.e., \(xs=\textit{nums}[0] \oplus \textit{nums}[1] \oplus \cdots \oplus \textit{nums}[n-1]\).
Next, we enumerate each element \(x\) in the array \(\textit{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^{\textit{maximumBit}}\).
That is to say, we start from the \(\textit{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(nm)\), and the space complexity is \(O(1)\), where \(n\) and \(m\) are the values of the array \(\textit{nums}\) and \(\textit{maximumBit}\) respectively.
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | |
Solution 2: Enumeration Optimization
Thinking
Solution 1 walks \(\textit{maximumBit}\) bits. The optimum sets every allowed bit of \(xs\oplus k\) to \(1\), so \(k=xs\oplus(2^{\textit{maximumBit}}-1)\). One XOR per query makes the scan linear.
Similar to Solution 1, we first preprocess the XOR sum \(xs\) of the array \(\textit{nums}\), i.e., \(xs=\textit{nums}[0] \oplus \textit{nums}[1] \oplus \cdots \oplus \textit{nums}[n-1]\).
Next, we calculate \(2^{\textit{maximumBit}} - 1\), which is \(2^{\textit{maximumBit}}\) minus \(1\), denoted as \(\textit{mask}\). Then, we enumerate each element \(x\) in the array \(\textit{nums}\) from back to front. The current XOR sum is \(xs\), then \(k=xs \oplus \textit{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)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).
1 2 3 4 5 6 7 8 9 10 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |