421. Maximum XOR value of two numbers in the array

421. The maximum exclusive or value of two numbers in an array

Original title link ：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/

Give you an array of integers nums , return nums[i] XOR nums[j] The largest operation result of , among 0 ≤ i ≤ j < n .

Advanced ： You can O(n) Is it time to solve this problem ？

Example 1：

Input ：nums = [3,10,5,25,2,8]
Output ：28
explain ： The maximum result is 5 XOR 25 = 28.
Example 2：

Input ：nums = [0]
Output ：0
Example 3：

Input ：nums = [2,4]
Output ：6
Example 4：

Input ：nums = [8,10,2]
Output ：10
Example 5：

Input ：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output ：127

Tips ：

1 <= nums.length <= 2 * 105
0 <= nums[i] <= 231 - 1

Their thinking ：

This problem is a bit operation , And apply a law ： If a ^ b = max establish ,max Indicates the current “ Maximum ”, Then there must be max ^ b = a establish . See code for specific implementation .

Code implementation ：

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        #  Mask , Bit operation , Used to get prefix , Initialize to 0
        mask = 0

        #  because  0 <= nums[i] <= 2 Of 31 Power  - 1
        #  loop 31 Next time , To get the maximum , So start from the highest position 
        for i in range(30, -1, -1):
            #  Get the mask from the high bit 
            mask |= (1 << i)

            #  Put prefixes into a hash table 
            s = set()
            #  Prefix is obtained by bitwise and operation through mask and number itself 
            #  Prefix saved to set Used in the following XOR result search 
            for num in nums:
                s.add(mask & num)

            #  Suppose that the largest XOR value starts from the high order 1
            #  So use ans To press or operate , Get a temporary XOR maximum temp
            #  Go to set Find whether it is in num There is a number in , and temp To perform exclusive or operations 
            #  Make the current bit 1
            temp = ans | (1 << i)

            #  Then according to the law ： If  a ^ b = max  establish  ,max  Indicates the current “ Maximum ”,
            #  Then there must be  max ^ b = a  establish 
            #  here temp As a max,prefix As a b,s The value in is regarded as a
            for prefix in s:
                if temp ^ prefix in s:
                    #  Update XOR Max 
                    ans = temp
                    break
            #  Clear this prefix 
            s.clear()

        return ans

reference ：
https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/solution/li-yong-yi-huo-yun-suan-de-xing-zhi-tan-xin-suan-f/