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.
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