Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

分析

a^b=c => a^c =b. 所以用ans^a = b => a^b = ans (a,b都是prevs)

每次这里只在乎每个Num的左半部分bit， ans >>=1 然后 ans^1（ 就是ans+1）让ans下一位变成1，如果能找到ans^a也在prevs里，这该数b^a = ans

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32)[::-1]:
            prevs = [n>>i for n in nums]
            ans <<= 1
            ans += any(ans^1^p in prevs for p in prevs)
        return ans

Trie实现，只有2个子树0,1。每次尽量往相反方向走，0^1才能max

可行则 temp+=1<<j. 或者直接最后叶子的值^当前Num

class TrieNode:
    def __init__(self):
        self.val = 0
        self.children = {}
       
class Solution:
    """
    @param nums: 
    @return: the maximum result of ai XOR aj, where 0 ≤ i, j < n
    """

    def findMaximumXOR(self, arr):
        root = TrieNode()
        
        for key in arr:
            node = root
            for i in range(31, -1, -1):
                curbit = key >> i & 1
                if curbit not in node.children:
                    node.children[curbit] = TrieNode()
                node = node.children[curbit]
            node.val = key
        
        
        res = 0
        for key in arr:
            node = root
            temp = 0
            for i in range(31, -1, -1):
                curbit = key >> i & 1
                
                if 1^curbit in node.children:
                    temp += 1 << i
                    node = node.children[1^curbit]
                elif curbit in node.children:
                    node = node.children[curbit]
            res = max(temp, res)
            
        return res