# leetcode 1829. Maximum XOR for Each Query（python）

2022-01-29 17:11:05

This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .

### describe

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 that nums XOR nums XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the ith 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 = , k = 3 since 0 XOR 3 = 3.
Copy code ``````

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 = , k = 5 since 2 XOR 5 = 7.
Copy code ``````

Example 3:

``````Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]
Copy code ``````

Note:

``````nums.length == n
1 <= n <= 10^5
1 <= maximumBit <= 20
0 <= nums[i] < 2^maximumBit
nums​​​ is sorted in ascending order.
Copy code ``````

### analysis

According to the meaning , Is to give a sorted length of n A list of integers nums , And gives an integer maximumBit, Let's take the following steps ：

• Before the 1 An element performs an operation , and [0, 2^ maximumBit-1] An integer or operation between can ensure the maximum result , Add this integer to the result list
• Before the 2 An element performs an operation , and [0, 2^ maximumBit-1] An integer or operation between can ensure the maximum result , Add this integer to the result list
• Before the 3 An element performs an operation , and [0, 2^ maximumBit-1] An integer or operation between can ensure the maximum result , Add this integer to the result list
• ......
• front n An element performs an operation , and [0, 2^ maximumBit-1] An integer or operation between can ensure the maximum result , Add this integer to the result list

Finally, return the result list .

The most direct way is to solve by violence , First solve all the elements before each position or the result , Then double loop to find the most suitable... For each position [0, 2^ maximumBit-1] Integer results between . But the result timed out . Because in the title n and maximumBit It's big .

``````class Solution(object):
def getMaximumXor(self, nums, maximumBit):
"""
:type nums: List[int]
:type maximumBit: int
:rtype: List[int]
"""
XORS = [nums]
for i,num in enumerate(nums[1:]):
XORS.append(XORS[-1] ^ num)
result = *len(nums)
for i,num in enumerate(XORS):
tmp = num ^ 0
for bit in range(1, 2**maximumBit):
if num^bit > tmp:
tmp = num^bit
result[i] = bit
return result[::-1]

Copy code ``````

### Running results

``````Time Limit Exceeded
Copy code ``````

### analysis

In fact, this is a question of investigation or operation , To solve a problem, you need to know two key knowledge points ：

• No matter how many [0, 2^maximumBit-1] The numbers in this range are or calculated , The biggest result can only be 2^maximumBit -1
• If x ^ y == z, that x ^ z == y, meanwhile y ^ z == x

Combined with the meaning of the question, we can get :

• nums Each element in the satisfies 0 <= nums[i] < 2^maximumBit
• k The value must meet or the maximum result is (2^maximumBit-1), therefore nums ^ nums ^ ... ^ nums[nums.length-1] ^ k == (2^maximumBit-1), that k == nums ^ nums ^ ... ^ nums[nums.length-1] ^ (2^maximumBit-1)

``````class Solution(object):
def getMaximumXor(self, nums, maximumBit):
"""
:type nums: List[int]
:type maximumBit: int
:rtype: List[int]
"""
ALL = 0
for num in nums: ALL ^= num
maxresult = 2**maximumBit-1
result = []
while nums:
result.append(ALL ^ maxresult)
ALL ^= nums.pop()
return result
Copy code ``````

### Running results

``````Runtime: 1113 ms, faster than 25.93% of Python online submissions for Maximum XOR for Each Query.
Memory Usage: 29.1 MB, less than 81.48% of Python online submissions for Maximum XOR for Each Query.
Copy code ``````