https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array

Let us try to build the biggest XOR number binary digit by digit. So, the first question we are going to ask, is there two numbers, such that its XOR starts with 1...... (length is 32 bits). Howe we can find it? Let us use the idea of Problem 1: TwoSum: put all prefixes of lengh one to set and then try to find two numbers in this set such that their XOR starts with 1 (at first we have at most 2 elements in our set). Imagine that there are two numbers, which XOR starts with 1......, then the next question is there are two numbers with XOR starts with 11....., we again iterate through all numbers and find two of them with XOR starts with 11. It can happen that on the next step we did not find XOR starts with 111....., then we do not change our ans and on next step we are looking for XOR starts with 1101... and so on. So:

  1. We iterate, starting from the first digit in binary representation of number and go to the right.
  2. For each traversed digit we update our binary mask: in the beginning it is 10000...000, then it is 11000...000, 11100...000 and in the end 11111...111. We need this mask to quickly extract information about first several digits of our number.
  3. Create set of all possible starts of numbers, using num & mask: on the first iterations it will be first digit, on the next one first two digits and so on.
  4. Apply TwoSum problem: if we found two numbers with XOR starting with start, then we are happy: we update our ans and break for inner loop: so we continue to look at the next digit.

Complexity: Time complexity is O(32n), because we traverse our numbers exactly 32 times. I do not like when this is called O(n) complexity, because we have quite big constant here. Space complexity is O(n).

class Solution:
    def findMaximumXOR(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

If you like the solution, you can upvote it on leetcode discussion section: Problem 0421