Maximum XOR of Two Numbers in an Array

Given an array of N non-negative integers (N >= 2), find the maximum value of arr[i] XOR arr[j] over all pairs of distinct indices i and j. The array can be large enough that checking every pair is too slow, so your solution must run well below O(N^2). Print the maximum XOR value found.

Input: The first line contains the integer N. The second line contains N space-separated non-negative integers, the array elements. Output: A single integer: the maximum XOR value achievable by any pair of distinct indices.

2 <= N <= 100000; 0 <= arr[i] <= 2^30 - 1 (1073741823)

This is the SAME bitwise-trie technique used for prefix-matching problems (like autocomplete), just repurposed to search for 'most different' rather than 'most similar' - recognizing that a trie's usefulness extends beyond string prefixes to any fixed-length bit-sequence matching problem is a valuable generalization.

Find the largest possible XOR value obtainable from any pair of numbers in an array, without checking every pair. Brute force: Check every possible pair of numbers directly, computing their XOR - this costs O(N²), too slow for N up to 100,000. Optimised: A bitwise trie lets you, for each number, GREEDILY search for its best XOR partner by always preferring the OPPOSITE bit at each level (maximizing the XOR bit by bit from the most significant bit down) - since the trie groups numbers by their shared bit prefixes, this greedy walk finds the true best partner for each number in O(bits) rather than comparing against every other number individually.

1. Build a BITWISE TRIE from the 30-bit binary representation of every number, inserting bit by bit from the MOST significant bit down. 2. For each number, greedily WALK the trie choosing the OPPOSITE bit at every level whenever that branch exists, to build the largest possible XOR bit by bit. 3. Whenever the opposite branch is missing, you're forced down the SAME-bit branch (which is always present, since the number itself is stored there).

Time: O(N * bits) - inserting all N numbers into the trie costs O(N * bits), and querying the best partner for each number also costs O(bits) per query. Space: O(N * bits), for the trie's nodes (each number contributes at most 'bits' new trie nodes).

All elements may be equal (the maximum XOR is then 0); the array may contain both 0 and the maximum allowed value, in which case their XOR equals that maximum value.

Be ready to explain WHY greedily choosing the opposite bit at every level is provably optimal - since XOR's most significant differing bit contributes the most to the final value, maximizing bits from the top down (rather than any other order) always yields the true maximum.