1420. The Expected Larger of Two Draws

Two integers are drawn independently and uniformly at random from 1 to n, with repeats allowed. Print the expected value of the larger of the two, as an exact reduced fraction.

n = 1 -> 1/1 only one outcome n = 2 -> 7/4 the four outcomes give maxima 1, 2, 2, 2 n = 3 -> 22/9 n = 6 -> 161/36 two fair dice, expected higher face

## The sign rule, pinned before anything is asserted

A fraction has more than one reduced spelling unless the sign is placed by a rule: -1/2 and 1/-2 are the same number. So this problem requires

• the denominator positive,
• the sign carried by the numerator,
• zero written exactly 0/1.

Without that sentence the five reference languages would disagree and the problem would be unanswerable rather than hard.

## What most people try first

Sum over the n^2 outcomes. With n at 10^9 that is 10^18 pairs. The first real improvement is to sum over the value of the maximum instead, which is n terms, but 10^9 terms per query is still too many and the answer must come from a closed form.

The other common attempt is to guess that the answer is (2/3)(n+1) or similar by analogy with the continuous case. It is close but wrong, and the difference is exactly the term the discrete tie contributes.

## Count the outcomes whose maximum is k

The maximum is at most k exactly when both draws are at most k, which is k^2 of the n^2 equally likely pairs. So the maximum is exactly k in k^2 - (k-1)^2 = 2k - 1 of them, and

E = (1/n^2) * sum over k = 1..n of k * (2k - 1) = (2 * sum k^2 - sum k) / n^2

Substituting the two standard closed forms sum k = n(n+1)/2 and sum k^2 = n(n+1)(2n+1)/6 and simplifying gives

E = (n + 1) * (4n - 1) / (6n)

which is O(1) to evaluate. Reduce it by the gcd of numerator and denominator.

## Why it is correct, by a second route

The same answer comes out of the complementary identity E[X] = sum over k >= 0 of P(X > k), which for a value in 1..n reads E = n - sum over k = 1..n-1 of P(max <= k). Since P(max <= k) = (k/n)^2,

E = n - (1/n^2) * sum over k = 1..n-1 of k^2 = n - (n-1)n(2n-1) / (6n^2) = n - (n-1)(2n-1) / (6n) = (6n^2 - 2n^2 + 3n - 1) / (6n) = (4n^2 + 3n - 1) / (6n) = (n + 1)(4n - 1) / (6n)

Two derivations with nothing in common arriving at the same expression is the check worth doing before trusting a closed form, and it is exactly what the oracle does: it computes the direct sum for small n and the complementary form for all n, and compares.

## Sanity checks on the formula

At n = 1 it gives 2 * 3 / 6 = 1, correct since there is one outcome. At n = 2 it gives 3 * 7 / 12 = 7/4, matching the four outcomes listed above. For large n it tends to 4n/6 = 2n/3, which is the continuous answer, so the formula degrades to the right limit.

## Overflow

(n + 1) * (4n - 1) with n at 10^9 is about 4 * 10^18. That fits a signed 64-bit integer, whose limit is 9223372036854775807, with a margin of only about a factor of two, and it does not fit a signed 32-bit one, whose limit is 2147483647: a 32-bit build answers 1348492799/1705032704 where the truth is 1333333334333333333/2000000000. Note that 4n alone is 4 * 10^9, which already does not fit 32 bits, while 2 * 10^9 would have. The denominator 6n reaches 6 * 10^9, also past 32 bits. In JavaScript the numerator is past 2^53, so BigInt is required.

## Cost

O(log n) per query, all of it in the gcd.

Constraints - `1 ≤ n ≤ 1000000000`