Python O(N) Trie Solution w/comments and explanations
The goal is to find 2 numbers in num that will produce the largest XOR, e.g. a number that has the most 1\'s to the left in its binary representation.  We can d
The goal is to find 2 numbers in num that will produce the largest XOR, e.g. a number that has the most 1\'s to the left in its binary representation.  We can do this by first building a trie that represents the binary form of the numbers in nums, then, for each num in nums, traverse the trie to find the number that will produce the largest XOR with it.\n\n```python\nclass Solution:\n    def findMaximumXOR(self, nums: List[int]) -> int:\n        # need to know the largest binary representation\n\t\t# bin prepends \'0b\', ignore\n\t\tL = len(bin(max(nums))) - 2\n\n\t\t# preprocess step - left-pad zeros to ensure each number has L bits\n\t\t# (x >> i) & 1 produces the bit at position i for number x\n\t\t# x\'s value is moved right by i bits, we & 1 to produce 0 or 1\n\t\t# e.g., if L = 5, then 3 = [0, 0, 0, 1, 1], so the steps to get there are:\n\t\t# (3 >> 4) & 1 = 0\n\t\t# (3 >> 3) & 1 = 0\n\t\t# (3 >> 2) & 1 = 0\n\t\t# (3 >> 1) & 1 = 1\n\t\t# (3 >> 0) & 1 = 1\n\t\tnums_bits = [[(x >> i) & 1 for i in reversed(range(L))] for x in nums]\n\t\troot = {}\n\t\t# build the trie\n\t\tfor num, bits in zip(nums, nums_bits):\n\t\t\tnode = root\n\t\t\tfor bit in bits:\n\t\t\t\tnode = node.setdefault(bit, {})\n\t\t\tnode["#"] = num\n\n\t\tmax_xor = 0\n\t\tfor num, bits in zip(nums, nums_bits):\n\t\t\tnode = root\n\t\t\t# we want to find the node that will produce the largest XOR with num\n\t\t\tfor bit in bits:\n\t\t\t\t# our goal is to find the opposite bit, e.g. bit = 0, we want 1\n\t\t\t\t# this is our goal because we want as many 1\'s as possible\n\t\t\t\ttoggled_bit = 1 - bit\n\t\t\t\tif toggled_bit in node:\n\t\t\t\t\tnode = node[toggled_bit]\n\t\t\t\telse:\n\t\t\t\t\tnode = node[bit]\n\t\t\t# we\'re at a leaf node, now we can do the XOR computation\n\t\t\tmax_xor = max(max_xor, node["#"] ^ num)\n\n\n        return max_xor\n```
['Trie', 'Python', 'Python3']