This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

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[0] XOR nums[1] 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, 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. 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.Copy the 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. 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. nums = [2], k = 5 since 2 XOR 5 = 7.Copy the code

Example 3:

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

Note:

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

parsing

Given a sorted list of integers of length N, nums, and given an integer maximumBit, let’s do the following:

  • Add the integer between the first element and [0, 2^ maximumbit-1] to the list of results that guarantees maximum results
  • Add the integer between the first two elements and [0, 2^ maximumbit-1] to the list of results that guarantees maximum results
  • Add the integer between [0, 2^ maximumbit-1] and the first three elements to the list of results, which guarantees maximum results
  • .
  • Add the first n elements to the list of results, and an integer between [0, 2^ maximumbit-1] that guarantees maximum results

Finally, a list of results is returned.

The most straightforward method is brute force solving, first solving or solving all the elements up to each position, and then double-cycling to find the integer between 0, 2^ maximumbit-1 that best fits each position. But this result runs out of time. Because both n and maximumBit are large.

answer

class Solution(object):
    def getMaximumXor(self, nums, maximumBit):
        """
        :type nums: List[int]
        :type maximumBit: int
        :rtype: List[int]
        """
        XORS = [nums[0]]
        for i,num in enumerate(nums[1:]):
            XORS.append(XORS[-1] ^ num)
        result = [0]*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 the code

The results

Time Limit Exceeded
Copy the code

parsing

There are two key things you need to know to solve this question:

  • No matter how many numbers are in the range [0, 2^ maximumbit-1], the maximum result can only be 2^ maximumbit-1
  • If x ^ y == z, then x ^ z == y, and y ^ z == x

We can get as follows:

  • Each element in numS satisfies 0 <= nums[I] < 2^maximumBit
  • Nums [0] ^ nums[1] ^… ^ nums[0] ^ nums[1] ^ k == (2^maximumBit-1), k == nums[0] ^ nums[1] ^… ^ nums[nums.length-1] ^ (2^maximumBit-1)

answer

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 the code

The results

Given in the Python online submissions with Each Query. Memory Usage: Submissions in the Python online list for Maximum XOR for Each Query.Copy the code

Original link: leetcode.com/problems/ma…

Your support is my biggest motivation