<p>Given an integer array <code>nums</code>, return <em>the maximum result of </em><code>nums[i] XOR nums[j]</code>, where <code>0 &lt;= i &lt;= j &lt; n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution:
    """
    exclusive OR
    0 0 - 0
    0 1 - 1
    1 0 - 1
    1 1 - 0

    either of bit is set
    """

    """
    brute force, check xor of each two element

    time: O(n**2)
    space: O(1)
    """
    def findMaximumXORBrute(self, nums: List[int]) -> int:
        pass

    """
    using trie


    """
    def findMaximumXOR(self, nums: List[int]) -> int:
        trie = [[], []] #  zero, one
        n = len(nums)

        def insert(root, num):
            # insert from msb to lower value, left to right
            for i in range(31, -1, -1):
                if num & 1<<i: # curr bit set
                    if not root[1]:
                        root[1] = [[], []]
                    root = root[1]  
                else: 
                    if not root[0]:
                        root[0] = [[], []]
                    root = root[0]
        
        """
        we basically want to get the number whose bit is opposite of the bits set in num
        """
        def find_max_xor(root, num):
            curr_xor = 0
            for i in range(31, -1, -1):
                curr_bit = 0 if (1<<i & num == 0) else 1
                opposite = 1 if (curr_bit == 0) else 0
                # print(f"{i} {curr_bit} {opposite} {curr_xor}, {root}")
                if root[opposite]:
                    curr_xor += 1<<i
                    root = root[opposite]
                else:
                    root = root[curr_bit]

            return curr_xor

        insert(trie, nums[0])
        max_xor = 0
        for i in range(1, n):
            max_xor = max(max_xor, find_max_xor(trie, nums[i]))
            insert(trie, nums[i])

        return max_xor

317803