<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:
    def findMaximumXOR(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0

        t = Trie()
        for num in nums:
            t.insert(num)

        return t.getMaxResult(nums)
        
class Trie:

    def __init__(self):
        self.mp = {}

    def binary_iter_32_reversed(self, num):
        """Generates 32 bits of a number in forward order."""
        for _ in range(32):
            yield (num >> 31) & 1
            num <<= 1

    def insert(self, num):
        trav = self.mp
        for b in self.binary_iter_32_reversed(num):
            if b not in trav:
                trav[b] = {}
            trav = trav[b]
        trav[-1] = {}

    def getMaxResult(self, nums):
        greatestSum = 0
        for num in nums:
            #print("\nnum",num,'\n')
            numSum = 0
            trav = self.mp
            pwr = 31
            for b in self.binary_iter_32_reversed(num):
                #print(pwr, b, list(trav.keys()))
                if b == 0 and 1 in trav:
                    trav = trav[1]
                    numSum += 2**pwr
                elif b == 1 and 0 in trav:
                    trav = trav[0]
                    numSum += 2**pwr
                else:
                    if 0 in trav:
                        trav = trav[0]
                    else:
                        trav = trav[1]
                pwr -= 1
            
            #idx == 0
            # if (b == 0 and 1 in trav) or (b == 1 and 0 in trav):
            #     numSum += 2^pwr
            greatestSum = max(greatestSum, numSum)

        return greatestSum
637396