421. Maximum XOR of Two Numbers in an Array

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array

Python

• XOR的特性： If a ^ b = c, then a ^ c = b, b ^ c = a are also True
• <<在Python中是往左移動一個bit；>>往右移動一個bit
  • 1 << 2會將001移動成100，因此得到十進位的4
  • 16 >> 2會將10000往右移動城100，得到十進位的4
• 因為題目的nums範圍太大直接liter會timeout，對32 bit做liter可以得到O(1)的時間複雜度

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        result = 0
        for bit in range(31, -1, -1):
            result <<= 1
            shifts = {num >> bit for num in nums}
            if any(result ^ 1 ^ num in shifts for num in shifts):
                result += 1
        return result