Binary tries for maximum XOR

A binary trie stores integers as paths of bits, the most significant bit first, so two numbers share a path for as long as their leading bits agree. It solves the maximum XOR of two numbers in an array in O(n × b) time for b-bit numbers: insert the numbers, and for each one walk down the trie, taking the opposite bit at every level where that child exists. The greedy choice works because a 1 in a higher bit of a XOR is worth more than all the lower bits together. For 30-bit numbers that is 30 steps per number, where checking every pair costs up to n − 1 XORs per number.

The problem: the most different pair of device IDs

• [41, 18, 7, 33, 60, 12] gives 59, from 41 and 18: 101001 XOR 010010 = 111011.
• [5, 9, 12, 3] gives 15, from 12 and 3: 1100 XOR 0011 = 1111, the largest four-bit value.
• [7, 7] gives 0: two devices with the same ID differ nowhere.

The brute force, and why it fails at these sizes

XOR every pair and keep the largest:

"""The brute force for the most different pair of device IDs: the XOR of every pair."""


def max_xor_brute(ids):
    """The largest a ^ b over pairs of different positions, the pair itself, and how many pairs were tried."""
    best, pair, tried = -1, None, 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            tried += 1
            if ids[i] ^ ids[j] > best:
                best, pair = ids[i] ^ ids[j], (ids[i], ids[j])
    return best, pair, tried


if __name__ == "__main__":
    for ids in ([41, 18, 7, 33, 60, 12], [5, 9, 12, 3], [7, 7]):
        best, (a, b), tried = max_xor_brute(ids)
        width = max(a, b, 1).bit_length()
        print(f"{ids}")
        print(f"  {a} ^ {b} = {best}: {a:0{width}b} ^ {b:0{width}b} = {best:0{width}b}, {tried} pair{'s' * (tried != 1)} tried")
    n = 200_000
    print()
    print(f"At the limits: {n:,} IDs make {n * (n - 1) // 2:,} pairs")

[41, 18, 7, 33, 60, 12]
  41 ^ 18 = 59: 101001 ^ 010010 = 111011, 15 pairs tried
[5, 9, 12, 3]
  12 ^ 3 = 15: 1100 ^ 0011 = 1111, 6 pairs tried
[7, 7]
  7 ^ 7 = 0: 111 ^ 111 = 000, 1 pair tried

At the limits: 200,000 IDs make 19,999,900,000 pairs

It is O(n²): n(n − 1)/2 = 19,999,900,000 pairs at n = 200,000. At the 10⁸ simple steps a second that the constraints lesson plans with, compiled code needs more than three minutes, and Python far longer.

What to notice

A XOR is large when its high bits are 1, and the top bit decides on its own: bit 29 is worth 2²⁹, more than 2²⁹ − 1, the sum of all the bits below it. So the best partner for a number differs from it as early as possible: first a partner whose top bit differs, then, among those, one whose next bit differs too, and so on. Numbers that share their top bits share a path in a binary trie, so each of those questions is a single step down it.

The trie and the greedy walk, step by step Pro: opens with a Pro, Premium or Ultimate pass