All problems

Maximum XOR Pair

Medium · trie

Given a list nums of non-negative integers, pick two entries at different positions and combine them with bitwise XOR (^). Return the largest XOR value you can get.

The two entries may hold equal values. If nums has only one entry, there is no pair to take, so return 0.

Recall that a ^ b has a 1 in every bit position where exactly one of a and b has a 1. For example, 6 ^ 1 = 7, because 110 and 001 differ in all three positions.

Examples

Example 1

Input: nums = [6, 1, 12]

Output: 13

The pairs give 6 ^ 1 = 7, 6 ^ 12 = 10 and 1 ^ 12 = 13. The largest is 13.

Example 2

Input: nums = [8, 8, 8]

Output: 0

Equal values cancel out, so every pair gives 0.

Example 3

Input: nums = [5]

Output: 0

A single entry has no pair, so the answer is 0.

Constraints