Most Different Pair

Medium

You are given an array of non-negative integers values. Choose two elements (the same element may be chosen twice) so that their bitwise XOR is as large as possible, and return that XOR. Trying every pair takes O(n²); aim for something faster.

Example 1

values=[6, 9, 4, 12] → 15

6 = 0110 and 9 = 1001 differ in all four bits: 6 XOR 9 = 15.

Example 2

values=[7, 7] → 0

Both numbers are equal, so their XOR is 0.

Example 3

values=[16, 3, 20, 2] → 23

The best is 3 XOR 20 = 23; for comparison, 2 XOR 20 = 22 and 16 XOR 3 = 19.

Constraints

1 ≤ len(values) ≤ 2·10⁵
0 ≤ values[i] ≤ 2³¹ − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Trie Array Hash Table

Similar problems

Words That Fit Each Puzzle Hard Best XOR Up the Chain of Command Hard XOR of a Close Pair Easy Largest XOR of a Close Pair Hard Split Into Dictionary Words Medium

Input

values=[6, 9, 4, 12]

Expected

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.