<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>. A pair of integers <code>x</code> and <code>y</code> is called a <strong>strong</strong> pair if it satisfies the condition:</p>

<ul>
	<li><code>|x - y| &lt;= min(x, y)</code></li>
</ul>

<p>You need to select two integers from <code>nums</code> such that they form a strong pair and their bitwise <code>XOR</code> is the <strong>maximum</strong> among all strong pairs in the array.</p>

<p>Return <em>the <strong>maximum</strong> </em><code>XOR</code><em> value out of all possible strong pairs in the array</em> <code>nums</code>.</p>

<p><strong>Note</strong> that you can pick the same integer twice to form a pair.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5]
<strong>Output:</strong> 7
<strong>Explanation:</strong> There are 11 strong pairs in the array <code>nums</code>: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.
</pre>

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

<pre>
<strong>Input:</strong> nums = [10,100]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are 2 strong pairs in the array nums: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.
</pre>

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

<pre>
<strong>Input:</strong> nums = [500,520,2500,3000]
<strong>Output:</strong> 1020
<strong>Explanation:</strong> There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000).
The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.
</pre>

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

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

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums = sorted(set(nums))
        bitcount_lsts = [[]]
        curr = 0
        # Partitioning the numbers based on their number of bits
        for num in nums:
            num2 = num >> curr
            while num2:
                num2 >>= 1
                curr += 1
                bitcount_lsts.append([])
            bitcount_lsts[curr].append(num)
        bc_diff_mx = -1
        bc_diff_lst = []
        # Finding the number of bits in the solution
        for bc in reversed(range(len(bitcount_lsts))):
            if bc + 1 < bc_diff_mx:
                # If we have already found a strong pair whose bitwise
                # xor has more bits than the larger numbers being
                # considered, we do not need to search further
                break
            if bc + 1 < len(bitcount_lsts) and bitcount_lsts[bc] and\
                    bitcount_lsts[bc + 1] and\
                    bitcount_lsts[bc + 1][0] <= (bitcount_lsts[bc][-1] << 1):
                break
            if not bitcount_lsts[bc]: continue
            # Identifying whether for numbers with bc bits contain
            # a pair whose xor has the same or more bits than the
            # current largest
            # We use the observations that any pair with the same
            # number of bits is a strong pair and the xor of the
            # smallest and largest numbers with bc bits has at least as
            # many bits as the xor of any pair of numbers with bc bits
            num = bitcount_lsts[bc][-1] ^ bitcount_lsts[bc][0]
            #print(f"{bitcount_lsts[bc]}, num = {num}")
            bc_diff = 0
            while num:
                num >>= 1
                bc_diff += 1
            if bc_diff < bc_diff_mx: continue
            elif bc_diff > bc_diff_mx:
                bc_diff_lst = []
                bc_diff_mx = bc_diff
            bc_diff_lst.append(bc)
        else:
            if not bc_diff_mx: return 0
            bc = -1
        # The solution has max(bc_diff_mx, bc + 1) bits
        res = 0
        Trie = lambda: defaultdict(Trie)
        if bc_diff_mx >= bc + 1:
            # Search the possibile solutions where the larger and
            # smaller numbers in the pair have the same number of
            # bits using tries
            # We use the observation that any pair with the same
            # number of bits is a strong pair
            for bc2 in bc_diff_lst:
                trie = Trie()
                for num in bitcount_lsts[bc2]:
                    bit_lst = [-1] * bc_diff_mx
                    for i in reversed(range(bc_diff_mx)):
                        bit_lst[i] = num & 1
                        num >>= 1
                    t = trie
                    for b in bit_lst:
                        t = t[b]
                    t = trie
                    ans = 0
                    for b in bit_lst:
                        ans <<= 1
                        if 1 - b in t.keys():
                            ans |= 1
                            t = t[1 - b]
                        else: t = t[b]
                    res = max(res, ans)
            if bc_diff_mx > bc + 1:
                return res
        # Search the possible solutions where the larger number has
        # exactly one more bit than the smaller number of the pair
        # using two pointer approach and a trie
        trie = Trie()
        idx1 = len(bitcount_lsts[bc]) - 1
        for num2 in reversed(bitcount_lsts[bc + 1]):
            # Adding every previously not included number with bc
            # bits that forms a strong pair with num2
            while idx1 >= 0 and\
                    bitcount_lsts[bc][idx1] << 1 >= num2:
                num1 = bitcount_lsts[bc][idx1]
                bit_lst1 = [-1] * bc
                for i in reversed(range(bc)):
                    bit_lst1[i] = num1 & 1
                    num1 >>= 1
                t = trie
                for b in bit_lst1:
                    t = t[b]
                idx1 -= 1
            if not trie: continue
            # Searching the trie for the largest possible xor of
            # any pair consisting of num2 and numbers with bc
            # bits in the trie
            bit_lst2 = [-1] * bc
            for i in reversed(range(bc)):
                bit_lst2[i] = num2 & 1
                num2 >>= 1
            t = trie
            ans = 1
            for b in bit_lst2:
                ans <<= 1
                if 1 - b in t.keys():
                    ans |= 1
                    t = t[1 - b]
                else: t = t[b]
            res = max(res, ans)
        return res
38100