Maximum XOR of Two Numbers in an Array

Problem Id: 421 Difficulty: Medium


Intuition

Solution


class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        mask = 0

        for i in range(31, -1, -1):
            mask = mask | (1 << i)
            visited = set()
            for num in nums:
                visited.add(num & mask)

            tmp = ans | (1 << i)
            for prefix in visited:
                if prefix ^ tmp in visited:
                    ans = tmp
                    break
        return ans