Maximum XOR of Two Numbers

Given a list of non-negative integers nums, return the maximum value of nums[i] XOR nums[j] over all pairs of different positions i != j. Return 0 if the list has fewer than two elements.

Examples

Input:  nums = [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: 5 XOR 25 = 28.

Input:  nums = [8, 1, 2, 12, 7, 6]
Output: 15

Constraints

• 0 <= len(nums) <= 2 * 10**4
• 0 <= nums[i] < 2**31
• Target: O(n * 31); the O(n**2) pairwise check is too slow for the largest tests

Goals

• Store integers bit by bit in a binary trie
• Greedily prefer the opposite bit from the most significant position down