<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 Trie():
    def __init__(self):
        self.d = {}

    def insert(self, word):
        cur = self.d
        for i in word:
            if i not in cur:
                cur[i] = {}
            cur = cur[i]
    
        # cur['.'] = True
        return

    def search(self, word):
        # need to make the maximum value of xor values betwen the two numbers
        # How to pick?
        # since xor operation, focus on getting different numbers as soon as possible
        cur = self.d
        xor_max = 0
        for i in word:
            j = i
            if i == '0':
                i = '1'
            else:
                i = '0'

            # important step here is shifting it left and adding 1 coz its different
            # else just shifting and adding 0
            if i in cur:
                xor_max = (xor_max << 1) | 1  # Shift left and add 1
                cur = cur[i]
            else:
                xor_max = (xor_max << 1) 
                cur = cur[j]

        return xor_max








class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        # store a trie data structure
        # as the number of bits

        def convert(num):
            s = ""
            while num > 0:
                if num % 2 == 1:
                    s += '1'
                else:
                    s += '0'
                num = num // 2

            s = s[::-1]
            while len(s) != 32:
                s = '0' + s
            return s

        final = []
        trie = Trie()
        for num in nums:
            s1 = convert(num)
            final.append(s1)
            trie.insert(s1)

        res = 0
        for num in final:
            res = max(res, trie.search(num) )

        return res
536953