985. The Best XOR Between Close Values

Two values p and r are CLOSE when

|p - r| <= min(p, r)

Given n values, print the largest XOR over all pairs of different positions that are close. Print -1 if no pair is close.

1 2 3 4 -> 7 3 and 4 are close, since 1 <= 3 5 6 25 -> 3 only 5 and 6 are close 1 2 -> 3 the gap of 1 equals the smaller value 1 3 -> -1 the gap of 2 exceeds the smaller value 7 -> -1 one value, so no pair at all

## The condition, rewritten

Suppose p <= r. Then min(p, r) is p and |p - r| is r - p, so the condition is

r - p <= p which is r <= 2p

So after sorting, a pair is close exactly when the larger is at most twice the smaller. That is a statement about a WINDOW in sorted order: for a fixed r, the partners are all the values in [r/2, r], and that window's left end moves forward as r does.

Note what this does to 0: r <= 2 * 0 forces r = 0, so a zero is close only to another zero.

## The sweep

Sort the values. Walk a right end j forward, and keep a trie holding exactly the values in the current window.

sort a left = 0, best = -1 for j from 0 to n-1: while left < j and 2 * a[left] < a[j]: remove a[left] from the trie; left = left + 1 if the trie is not empty: best = max(best, bestXorAgainstTrie(a[j])) insert a[j]

Query before inserting, as in problem 979, so a[j] is never its own partner.

## Why removal is needed and how it is done

Values leave the window as j advances, so the trie must support deletion. This is exactly problem 978's structure: a counter at every node, decremented along the path, with the greedy walk treating a child whose counter is 0 as absent. No node is ever physically removed.

## Why the two pointers never go backwards

Sorting makes a[j] non-decreasing, so the condition 2 * a[left] < a[j], once true for some left, stays true for every larger j. A value that has left the window can never come back, so left only moves forward and each value is inserted once and removed at most once. That is the O(n) amortised argument, and it is the same one behind every two pointer sweep in this bank.

## Why maximising over a window still needs the trie

The window is contiguous in sorted order, but the best XOR inside it is not at either end: sorting arranges values by SIZE, and XOR is about differing bits. Problem 977 shows the one case where sorted order alone settles the answer, the minimum, and this is the other case, where it does not.

## The boundaries

A single value prints -1, and so does any input where no pair is close. best therefore starts at -1 and not at 0, because 0 is a legitimate answer, produced by any two equal values, which are always close to each other.

## Overflow

Nothing here overflows. Values and answers stay below 2^30 = 1073741824, and 2 * a[left] reaches at most 2147483646, which is still inside the 2147483647 limit of a signed 32 bit integer. It is one below the limit, so the comparison is safe as written, and writing it as a[left] < a[j] - a[left] avoids relying on that margin.

## Cost

Sorting is O(n log n). The sweep does at most n insertions and n removals and n queries, each 30 steps, so O(30 n). Space is at most 1 + 30 n = 3000001 nodes.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ each value ≤ 1073741823`, which is `2^30 - 1` - Values may repeat, and two equal values are always close to each other.