421. Maximum XOR of Two Numbers in an Array

Problem Link

Description

---

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

 

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

 

Constraints:

• 1 <= nums.length <= 2 * 105
• 0 <= nums[i] <= 231 - 1

Solution

---

Python3

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        N = len(nums)
        MAX_BIT = max(nums).bit_length()
        root = [None, None]
        res = 0
 
        def add(x):
            curr = root
 
            for k in range(MAX_BIT, -1, -1):
                if x & (1 << k) > 0:
                    bit = 1
                else:
                    bit = 0
                
                if curr[bit] is None:
                    curr[bit] = [None, None]
                
                curr = curr[bit]
        
        def query(x):
            res = 0
            curr = root
 
            for k in range(MAX_BIT, -1, -1):
                if x & (1 << k) > 0:
                    bit = 1
                else:
                    bit = 0
 
                opp = 1 - bit
 
                if curr is not None and curr[opp] is not None:
                    res += (1 << k)
                    curr = curr[opp]
                else:
                    if curr is None:
                        curr = [None, None]
                    curr = curr[bit]
 
            return res
 
        for x in nums:
            res = max(res, query(x))
            add(x)
        
        return res