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 < 2maximumBit
such thatnums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k
is maximized.k
is the answer to theith
query. - 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 == n
1 <= n <= 105
1 <= maximumBit <= 20
0 <= nums[i] < 2maximumBit
nums
is sorted in ascending order.
Solution: Prefix XOR
Compute s = nums[0] ^ nums[1] ^ … nums[n-1] first
to remove nums[i], we just need to do s ^= nums[i]
We can always maximize the xor of s and k to (2^maxbit – 1)
k = (2 ^ maxbit – 1) ^ s
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: vector<int> getMaximumXor(vector<int>& nums, int maximumBit) { const int t = (1 << maximumBit) - 1; const int n = nums.size(); vector<int> ans(n); int s = 0; for (int x : nums) s ^= x; for (int i = n - 1; i >= 0; --i) { ans[n - i - 1] = t ^ s; s ^= nums[i]; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment