Problem statement

https://binarysearch.com/problems/Max-XOR-of-Two-Integers/

Solution

Equal to Leetcode 0421. Maximum XOR of Two Numbers in an Array.

Complexity

It is O(n * log M) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        ans, mask = 0, 0
        for i in range(31, -1, -1):
            mask |= 1<<i
            found = set([num & mask for num in nums])
                
            start = ans | 1<<i
            for pref in found:
                if start^pref in found:
                    ans = start
                    break
         
        return ans