<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 TrieNode:

#     def __init__(self):
#         self.data: dict = {}

class Trie:

    def __init__(self):
        self.root = {}
    
    def insert(self, num: int):

        temp = self.root

        for i in range(32):

            # Shift left most bit of num
            # And check what is the bit
            checkBit = (num >> (31 - i)) & 1
            # 1 (num) & 1 => 1
            # 0 (num) & 1 => 0

            if checkBit not in temp:
                temp[checkBit] = {}
            temp = temp[checkBit]
        temp = {'#'}
    
    def maxXORNum(self, num):

        temp = self.root
        maxXor = 0
        for i in range(32):

            numBit = (num >> (31 - i)) & 1
            oppNumBit = 1 - numBit
            # 1 - 1 (numBit) = 0
            # 1 - 0 (numBit) = 1

            if oppNumBit in temp:
                # numBit xor oppNumBit => 1
                # more '1s' in maxXor == Larger number
                # Place '1' in the (31 - i)th Bit in the MaxXor
                # Because we have "oppNumBit" in our "trie" for "numBit" of "num"
                # For the (31 - i)th Bit for both "oppNumBit" and "numBit"
                # Hence, the addition of 1 should happen in the (31 - i)th bit of maxXor

                # Add '1' due to oppNumBit in maxXor.
                # To do that have to use '|' or operator
                maxXor = maxXor | (1 << (31 - i))

                # Becuase we have selected the "oppNumBit"
                temp = temp[oppNumBit]
            else:
                # Because no oppNumBit present in 'trie'
                temp = temp[numBit]
            
        return maxXor


# class Trie:
    
#     def __init__(self):
#         self.root = {}
#         # self.root = TrieNode()

#     # O(32)
#     # Maintaining Tries of size 32 bits. 31th, 30th, 29th .......... 0th
#     def insert(self, num: int):

#         temp = self.root
#         # check the bits 1 by 1 from right to left
#         for i in range(32):
#             # (31 - ith)th bit
#             # Left shift '1' 31 - i times '&' it with 31 - i th bit of the num
#             # Don't get 1 diorectly. If its not 0 its set else not set. You get not set directy.
            
#             # checkBit = 1 if num & (i << (31 - i)) != 0 else 0

#             # or
#             # Right Shift num '31 - i' times to get it to the 0th index
#             # '&' it with '1' to check.
#             # You will get 1 / 0 directly. [Advantage]
#             checkBit = num >> (31 - i) & 1

#             if checkBit not in temp.data:
#                 temp.data[checkBit] = TrieNode()
#             temp = temp.data[checkBit]
    
#     # O(32)
#     # Max XOR
#     def getTheMaxXOR(self, num: int):
        
#         maxNum = 0

#         # Temp needs to go accordingly that is from 31th .... 0th Bit
#         temp = self.root
#         for i in range(32):

#             checkBit = num >> (31 - i) & 1
#             # To get opposite in binary do 1 - bit
#             # 1 - 0(bit) => 1
#             # 1 - 1(bit) => 1
#             oppositeBit = 1 - checkBit

#             # We need xor. so if we get the opposie bit than the number.
#             # Then our answer in that bit will be 1.
#             # 1 xor 0 -> 1
#             # 0 xor 1 -> 1

#             # If opposite bit present in the temp trie node.
#             if oppositeBit in temp.data:
#                 # Then we can add 1 to our answer.
#                 # Initially maxNum -> 000000..... 31th 0
#                 # So the moment we get a opposite bit
#                 # We add it to the existing maxNum.
#                 # As the more 1's in the binary, bigger the number.
#                 # Example -> (maxnum) 00000, 01000, 01010, 01011

#                 # Updating the '31 - ith' bit with 1. Because we got 1(as oppositeBit is present) due to the xor.
#                 # We are preserving the existing bits in maxnum while setting 1 in '31 - i'th bit,
#                 # using '|' (or) operator. 
#                 maxNum = maxNum | (1 << (31 - i))

#                 # Go to the opposite node
#                 temp = temp.data[oppositeBit]
#             else:
#                 # Cannot update maxnum bit 1.
#                 # As no opposite bit present.
#                 # Continue with the zero bit
#                 temp = temp.data[checkBit]
        
#         return maxNum

# O(32*len(nums)) + O(32*len(nums))
# S.C Not specific
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:

        trie = Trie()

        # O(32 * len(nums))
        # Insert All the nums into the Trie
        for num in nums:
            trie.insert(num)
        
        maxNum = 0
        
        # O(32 * len(nums))
        # Get the max XOR among all the nums.
        # Don't have to care of the same number case because x ^ x => 0. Default situation.
        for num in nums:
            maxNum = max(maxNum, trie.maxXORNum(num))
        
        return maxNum
582609