Largest XOR of a Close Pair

Hard

You are given an array of positive integers values. Two numbers x and y are **close** if |x − y| ≤ min(x, y). Pick two numbers from the array that form a close pair so that their bitwise XOR is as large as possible, and return that XOR. You may pick the same element twice (such a pair is always close and its XOR is 0).

Example 1

values=[3, 5, 6, 12] → 10

The close pairs of different numbers are (3, 5), (3, 6), (5, 6) and (6, 12), with XORs 6, 5, 3 and 10. (5, 12) is not close since 7 > 5. The answer is 10.

Example 2

values=[1, 8] → 0

1 and 8 are not close (7 > 1), so only pairs of a number with itself remain, and their XOR is 0.

Constraints

1 ≤ len(values) ≤ 5 · 10⁴
1 ≤ values[i] < 2²⁰

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Trie Array Hash Table Sliding Window

Similar problems

XOR of a Close Pair Easy Words That Fit Each Puzzle Hard Best XOR Up the Chain of Command Hard Most Different Pair Medium Every Way to Space the Words Hard

Input

values=[3, 5, 6, 12]

Expected

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