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.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     def findMaximumXOR(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         ans = 0
         for bit in range(31, -1, -1) :
             ans = (ans << 1) + 1
             pre = set()
             for n in nums :
                 p = (n >> bit) & ans
                 if p in pre :
                     break
                 pre.add(ans - p)
             else :
                 ans -= 1
         return ans

class Solution:
     def findMaximumXOR(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         ans = 0
         for bit in range(31, -1, -1) :
             ans = (ans << 1) | 1
             pre = set()
             for n in nums :
                 p = (n >> bit) & ans
                 if p in pre :
                     break
                 pre.add(ans ^ p)
             else :
                 ans ^= 1
         return ans