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

import enum
import json
import math
from typing import List, Dict

import numpy as np


class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        n_digits = max([math.ceil(math.log2(e)) + 1 for e in nums])
        bin_nums = [to_binary_string(e, n_digits) for e in nums]
        tree = TreeNode(n_digits)
        for digits in bin_nums:
            tree.add_number(digits)
        scores = []
        best_additions = set()
        difficulty = {}
        for i, e in enumerate(bin_nums):
            if e in best_additions:
                continue
            # print(f"{i + 1} / {len(bin_nums)}")
            best_addition = tree.find_best_strong_addition(e)
            best_additions.add(from_binary_string(best_addition))
            scores.append(pair_score(e, best_addition))
            difficulty[e] = tree.current_calls
        # print([k for k, v in difficulty.items() if v == max(difficulty.values())])
        # print(sorted(set(difficulty.values())))
        return max(scores)


class TreeNode:
    def __init__(self, max_digits: int, current_level: int = 0, root=None):
        self.root = self if root is None else root
        self.current_calls = 0
        self.__current_level = current_level
        self.__max_digits = max_digits
        self.__children: Dict[str, TreeNode] = {}

    def __getitem__(self, item: str):
        return self.__children[item]

    def __contains__(self, item: str):
        return self.__children.__contains__(item)

    def __setitem__(self, key: str, value: "TreeNode"):
        self.__children[key] = value

    def add_number(self, digits: str):
        if len(digits) == 0:
            return
        if digits[0] not in self:
            self[digits[0]] = TreeNode(self.__max_digits, current_level=self.__current_level + 1, root=self.root)
        self[digits[0]].add_number(digits[1:])

    def find_best_strong_addition(self, digits: str):
        self.current_calls = 0
        return self._find_best_strong_addition(digits, found_digits='')

    def _find_best_strong_addition(self, digits: str, found_digits: str):
        # if digits == '00101000001101010111':
        #     print(digits, self.__current_level, found_digits)
        self.root.current_calls += 1
        number_comparison = NumbersComparison.compare_numbers_by_leading_digits(
            digits, found_digits, total_digits=self.__max_digits)
        if number_comparison == NumbersComparison.strong:
            return found_digits + self._find_best_addition(digits[len(found_digits):])
        elif number_comparison == NumbersComparison.weak:
            return None

        if len(found_digits) == self.__max_digits:
            return found_digits

        best_addition_0 = self['0']._find_best_strong_addition(
            digits, found_digits=found_digits + '0') if '0' in self else None
        best_addition_1 = self['1']._find_best_strong_addition(
            digits, found_digits=found_digits + '1') if '1' in self else None

        score_0 = pair_score(best_addition_0, digits) if best_addition_0 is not None else None
        score_1 = pair_score(best_addition_1, digits) if best_addition_1 is not None else None

        if score_0 is None:
            return best_addition_1
        elif score_1 is None:
            return best_addition_0
        else:
            if pair_score(best_addition_0, digits) > pair_score(best_addition_1, digits):
                return best_addition_0
            else:
                return best_addition_1

    def _find_best_addition(self, digits: str):
        if len(digits) == 0:
            return ''
        best_digit = reverse_digit(digits[0])
        if best_digit in self:
            return best_digit + self[best_digit]._find_best_addition(digits[1:])
        else:
            return digits[0] + self[digits[0]]._find_best_addition(digits[1:])

    def _descend(self, digits: str):
        if len(digits) == 0:
            return self
        return self[digits[0]]._descend(digits[1:])


class NumbersComparison(enum.Enum):
    strong = 'STRONG'
    weak = 'WEAK'
    more_digits_needed = 'MORE_DIGITS_NEEDED'

    @classmethod
    def compare_numbers_by_leading_digits(cls, digits_1: str, digits_2: str, total_digits: int):
        if len(digits_1) == len(digits_2) == total_digits:
            num_1 = from_binary_string(digits_1)
            num_2 = from_binary_string(digits_2)
            if abs(num_1 - num_2) <= min(num_1, num_2):
                return NumbersComparison.strong
            else:
                return NumbersComparison.weak

        if any([len(digits) < 2 for digits in (digits_1, digits_2)]):
            return NumbersComparison.more_digits_needed

        if len(digits_1) >= len(digits_2):
            digits_1 = digits_1[:len(digits_2)]
        else:
            digits_2 = digits_1[:len(digits_1)]

        first_one_index_1 = digits_1.find('1')
        first_one_index_2 = digits_2.find('1')

        if first_one_index_1 == first_one_index_2:
            if first_one_index_1 == -1:
                return NumbersComparison.more_digits_needed
            else:
                return NumbersComparison.strong

        if from_binary_string(digits_1) < from_binary_string(digits_2):
            fewest_digits, largest_digits = digits_1, digits_2
        else:
            largest_digits, fewest_digits = digits_1, digits_2

        if from_binary_string(largest_digits[:-1]) < from_binary_string(fewest_digits[1:]):
            return NumbersComparison.strong
        elif from_binary_string(largest_digits[:-1]) > from_binary_string(fewest_digits[1:]):
            return NumbersComparison.weak
        else:
            return NumbersComparison.more_digits_needed


def reverse_digit(digit: str):
    if digit == '0':
        return '1'
    elif digit == '1':
        return '0'
    else:
        raise Exception


def to_binary_string(num, n_digits):
    digits = bin(num)[2:]
    if len(digits) > n_digits:
        raise Exception
    digits = '0' * (n_digits - len(digits)) + digits
    return digits


def from_binary_string(digits: str):
    return int(digits, 2)


def pair_score(digits_1: str, digits_2: str):
    num_1, num_2 = int(digits_1, 2), int(digits_2, 2)
    return num_1 ^ num_2


class Solution:
    def maximumStrongPairXor(self, A: List[int]) -> int:
        res = 0
        for i in range(20, -1, -1):
            # 0011 -> 00110 Shift left
            res <<= 1
            pref, pref2 = {}, {}
            for a in A:
                p = a >> i
                if p not in pref:
                    pref[p] = pref2[p] = a
                pref[p] = min(pref[p], a)
                pref2[p] = max(pref2[p], a)
            for x in pref:
                # greedy guess
                y = res ^ 1 ^ x
                if x >= y and y in pref and pref[x] <= pref2[y] * 2:
                    # 00110 -> 00111 Add one to last bit
                    res |= 1
                    break
        return res


53300