421. Maximum XOR of Two Numbers in an Array

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.

class Solution:

    
    def findMaximumXOR_Hashset(nums):       

        B = len(bin(max(nums))) - 2        

        max_xor = 0

       

        for i in range(B, -1, -1):            

            max_xor = max_xor << 1            

            mask = max_xor | 1            

            prefixes = {num >> i for num in nums}

           

            for p in prefixes:

                q = p ^ mask

                if q in prefixes:

                    max_xor = max_xor | 1

       

        return max_xor

    def findMaximumXOR(nums):

        B = len(bin(max(nums))) - 2

        num_bits = []

        for n in nums:

            bits = []

            for b in range(B):

                bits.append((n >> b) & 1)

            num_bits.append(reversed(bits))

           

        max_xor = 0

        trie = {}

        for bits in num_bits:

            node = trie

            xor_node = trie

            cur_xor = 0

            for bit in bits:

                if bit not in node:

                    node[bit] = {}

                node = node[bit]

               

                opposit_bit = 1 - bit

                if opposit_bit in xor_node:

                    cur_xor = ( cur_xor << 1 ) | 1

                    xor_node = xor_node[opposit_bit]

                else:

                    cur_xor = ( cur_xor << 1 )

                    xor_node = xor_node[bit]

           

            max_xor = max(max_xor, cur_xor)

        return max_xor