200. Maximum XOR of Two Numbers in an Array

Given an array of n non-negative integers, find the maximum value of arr[i] XOR arr[j] over any pair of elements (i can equal j, though pairing an element with itself is never optimal unless the array is all zeros).

Input: The first line contains an integer n. The second line contains n space-separated non-negative integers. Output: Print a single integer - the maximum XOR value obtainable from any pair of elements in the array.

1 <= n <= 10^5, 0 <= arr[i] <= 10^9

The greedy 'always prefer the opposite bit, starting from the most significant bit' strategy works specifically because bit positions have exponentially different WEIGHTS - getting the highest bit right matters more than getting every lower bit right combined.

Among all possible pairs of numbers in an array, find the pair whose XOR (a bit-flipping comparison operation) gives the LARGEST possible result. Brute force: Compare every pair of numbers directly, compute their XOR, and keep the maximum - this costs O(n²), which becomes slow once the array has tens of thousands of elements. Optimised: A trie built from the numbers' BINARY representations lets you, for any given number, GREEDILY search for the number that differs from it as much as possible at the MOST SIGNIFICANT bits first (since higher bit positions contribute far more to the final value than lower ones) - this turns an O(n²) pairwise comparison into roughly O(n * bit-width), since each number's best match is found via one trie walk instead of comparing against every other number individually.

Compare every pair of elements (i, j) with two nested loops, compute arr[i] XOR arr[j] for each, and keep track of the maximum seen. This directly checks every possible pairing so it's obviously correct, but with n up to 10^5 the O(n^2) pair count (up to 10 billion) is far too slow. Time: O(n^2) Space: O(1)

Insert every number into a binary trie, one bit at a time from the most significant bit to the least, where each trie node has at most two children (for bit 0 and bit 1). Then, for each number, greedily walk the trie trying to go the opposite direction of that number's current bit at every level (to maximize the XOR at that position), falling back to the same-direction child only if the opposite doesn't exist, and accumulate the resulting XOR value. Taking the best result over all numbers gives the maximum pairwise XOR. This builds the trie once and answers each query with a single O(log(max(arr))) descent, avoiding the repeated hash-set rebuilding of the bitmask approach. Time: O(n * log(max(arr))) Space: O(n * log(max(arr)))

Build the answer one bit at a time from the most significant bit down. Maintain a running 'best prefix so far'; at each bit position, tentatively set that bit in the candidate answer and check whether some pair of numbers' prefixes (truncated to the bits considered so far) can actually achieve it, using a hash set of prefixes seen so far rebuilt at each bit level. If no pair achieves it, leave that bit as 0 and move to the next bit. This narrows the search using bit-level reasoning across about 30 passes over the array instead of examining all O(n^2) pairs directly. Time: O(n * log(max(arr))) Space: O(n)

1. Insert every number's binary representation into a trie, one bit at a time, starting from the MOST significant bit (the highest place value). 2. For each number, walk back down the trie trying to take the OPPOSITE bit at every single position (since XOR-ing with an opposite bit gives you a 1 at that position, which is what maximizes the result). 3. If the opposite-bit branch doesn't exist at some point, you're forced to take the SAME-bit branch instead (contributing a 0 at that position). 4. Track the best XOR value found across every number's greedy walk - that's the maximum.

Time: Roughly n times the number of bits per number (about 30-32) - for large arrays, dramatically faster than comparing every pair directly. Space: Proportional to n times the bit-width, for storing all numbers' binary paths in the trie.

Test n=1 (the only pair XORs the element with itself, giving 0), an array of all zeros (max XOR is 0), and n=10^5 with values up to 10^9 for performance.

This is a genuinely advanced trie application - be ready to explain WHY greedily choosing the opposite bit at each step (starting from the most significant bit) is provably optimal for maximizing XOR, since higher bit positions dominate the final numeric value.