983. The kth Largest XOR Among All Pairs

Given n values, consider all n (n - 1) / 2 XORs of pairs of different positions, with repeats kept. Print the kth largest of them.

1 4 2 7, k = 1 -> 6 the six pair values are 6 6 5 5 3 3 1 4 2 7, k = 6 -> 3 7 7 7, k = 2 -> 0 1 2 4 8, k = 3 -> 12

k = 1 is the question problem 976 answers and k at the last position is the question problem 977 answers, so this contains both as special cases and cannot be solved by either method.

## Listing the pairs is out of reach

At n = 20000 there are 20000 * 19999 / 2 = 199990000 pair values, so building and sorting them is two hundred million numbers, about 800 MB as 32 bit integers before the sort even starts.

## Search for the answer instead of computing it

Let atLeast(t) be the number of pairs whose XOR is at least t. As t grows, atLeast(t) never grows: raising the bar can only disqualify pairs. That makes it a monotone predicate, and the kth largest value is

the largest t with atLeast(t) >= k

which is a binary search over t in 0 .. 2^30 - 1, about 30 iterations.

## Why that t is exactly the kth largest

Write the pair values in non-increasing order as v1 >= v2 >= ... . For t = vk every one of v1 .. vk is at least t, so atLeast(vk) >= k. For t = vk + 1, the pairs at least t are exactly those strictly greater than vk, and there are fewer than k of them, since vk itself is not one. So vk satisfies the condition and vk + 1 does not, which makes vk the largest t that does.

## Where the counter comes from

atLeast(t) is the total number of pairs minus the number below t, and the number below t is exactly what problem 980 computes with one counted binary trie:

atLeast(t) = n (n - 1) / 2 - below(t)

Build the trie once, before the search, since it depends only on the values. Then each of the roughly 30 binary search steps costs one below call, which is O(30 n).

## Cost, computed

Building: 30 n insertions. The search: about 30 iterations, each summing countLess over n values at 30 steps each, so 30 * 30 * n. At n = 20000 that is 30 * 30 * 20000 = 18000000 steps, which is why n is capped lower here than in problem 980.

## Overflow

k can be as large as 20000 * 19999 / 2 = 199990000, which does fit in a signed 32 bit integer. The intermediate sums inside below do not: they reach roughly 2 * 199990000 + n, about 4 * 10^8 here, which still fits, but the habit of a 64 bit accumulator is what keeps this correct if n is ever raised, and it is what problem 980 needs outright at its own larger limit.

The answer itself is below 2^30 = 1073741824 and is comfortable in 32 bits.

## The boundary

k equal to the total number of pairs asks for the smallest pair value, and the binary search must be able to return 0, which it does when atLeast(0) is the total. Starting the search at lo = 0 rather than 1 is what allows that.

Constraints - `2 ≤ n ≤ 20000` - `0 ≤ each value ≤ 1073741823`, which is `2^30 - 1` - `1 ≤ k ≤ n (n - 1) / 2` - Values may repeat.