980. Counting Pairs Whose XOR Is Below a Limit

Given n values and a limit L, count the pairs of different positions whose XOR is strictly less than L.

1 4 2 7, L = 4 -> 2 the pairs giving 3 and 3 7 7 7, L = 1 -> 3 all three pairs give 0 1 2 4, L = 0 -> 0 nothing is below 0 1 2 4 8, L = 16 -> 6 every pair qualifies

## Maximising was a walk, counting is a walk that adds as it goes

Problem 973's greedy walks one path and takes one child at each step. A count cannot do that: at each bit, one of the two children may hold values that ALL qualify, and those have to be added in bulk rather than visited.

Store a counter at every node, as in problem 974, and then for one value x count the stored y with x XOR y < L like this.

countLess(x, L): node = root, total = 0 for b from 29 down to 0: if node is absent: stop xb = (x >> b) & 1 if the bit of L at b is 1: # taking the child equal to xb makes the XOR bit 0, below L's 1, # so every value under it qualifies whatever happens lower down total += cnt[child[node][xb]] node = child[node][1 - xb] # XOR bit 1, still tied with L else: # L has 0 here, so the XOR must have 0 here too node = child[node][xb] return total

## Why the two branches are exactly right

At each step the walk stands on the values whose XOR with x has matched L bit for bit so far. Then, at bit b:

· If L has a 1 there, a value making the XOR bit 0 is already strictly below L, whatever its lower bits are, because they are compared only after a position where it is already smaller. So the whole subtree counts, and the counter gives its size in one read. A value making the XOR bit 1 is still tied, so the walk continues into it. · If L has a 0 there, a value making the XOR bit 1 is already strictly ABOVE L and none of its subtree can qualify. Only the tied branch survives.

Reaching the bottom still tied means the XOR equals L exactly, which is not less than L, so nothing is added there. That is why L = 1073741823 against the pair 0, 1073741823 counts 0.

## From one value to all pairs

Build the trie with all n values, then sum countLess(x, L) over every x. Each unordered pair {i, j} is counted twice, once from each end, and each value counts ITSELF once when L is positive, since x XOR x = 0. So

pairs = (total - n) / 2

Handle L <= 0 by answering 0 without building anything, since no XOR is negative, and L > 1073741823 by answering n (n - 1) / 2, since every XOR is below that and the 30 bit walk cannot represent a limit that large.

## Overflow, computed

The answer needs 64 bits. At n = 100000 every pair can qualify, and

100000 * 99999 / 2 = 4999950000

which is about 2.3 times 2147483647, the largest signed 32 bit integer. The intermediate total is twice that plus n, close to 10^10, so the accumulator inside the summation loop must be 64 bit as well, not only the final answer.

The VALUES, by contrast, all stay below 2^30 and never need more than 32 bits, which is the trap: the data is small and the count is not.

## Cost

Building is O(30 n) and the summation is O(30 n) more, about 6 million steps at the limits. Space is at most 1 + 30 n = 3000001 nodes.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ each value ≤ 1073741823`, which is `2^30 - 1` - `0 ≤ L ≤ 1073741824`, which is `2^30` - Values may repeat.