Maximum XoR of Two Numbers in an Array

Cost: 6 hours

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Method 1: Use Trie

And then do a O(n) scan of binary complement on each element

Method 2: Iterative Hashmap for dominant bit

def findMaximumXOR(self, nums):
        ans = 0
        for i in reversed(range(32)):
            prefixes = set([x >> i for x in nums])
            ans <<=1
            candidate = ans + 1
            for p in prefixes:
                if candidate ^ p in prefixes:
                    ans = candidate
                    break      
        return ans

Method 2

Example input: [42, 5, 69, 22, 23, 8, 1, 17, 30, 75, 99]

The max XOR value is (30 ^ 99) = 125. Below are the binary represntations of each number.

42 = 0 1 0 1 0 1 0

5 = 0 0 0 0 1 0 1

69 = 1 0 0 0 1 0 1

22 = 0 0 1 0 1 1 0

23 = 0 0 1 0 1 1 1

8 = 0 0 0 1 0 0 0

1 = 0 0 0 0 0 0 1

17 = 0 0 1 0 0 0 1

30 = 0 0 1 1 1 1 0

75 = 1 0 0 1 0 1 1