# UVa 10288

## Summary

There are ${\displaystyle n}$ different kinds of coupons. Each box contains one coupon of random type. What's the

expected number of boxes you need in order to collect at least one coupon of every kind?

## Explanation

Suppose, you already have ${\displaystyle n-k}$ distinct coupons. Let ${\displaystyle a_{k}}$ denote the expected number of boxes you still need to collect the remaining ${\displaystyle k}$ coupons.

With probability ${\displaystyle {(n-k)/n}}$ the next coupon will be useless to you, and with probability ${\displaystyle {k/n}}$ it will be of the kind, which you don't yet have. Or, mathematically:

${\displaystyle a_{k}=(1+a_{k})\cdot {n-k \over n}+(1+a_{k-1})\cdot {k \over n}}$ ${\displaystyle =1+{n-k \over n}a_{k}+{k \over n}a_{k-1}}$, ${\displaystyle a_{0}=0}$.

Simplifying, you can obtain this simple formula for the answer:

${\displaystyle a_{n}=n\sum _{k=1}^{n}{1 \over k}}$

## Gotchas

• Standard 32-bit int's are not big enough for this problem, but 64-bit integers with gcd should be sufficient.

## An Alternative Explanation

As above, suppose you already have ${\displaystyle n-k}$ distinct coupons. Let ${\displaystyle X_{k}}$ denote the number of cereal boxes that you need to collect the ${\displaystyle k}$ remaining coupons. Let ${\displaystyle Y_{k}}$ denote the number of cereal boxes that you need to collect 1 of the ${\displaystyle k}$ coupons that you don't have yet.

Based on these definitions, the following equation holds:

${\displaystyle X_{k}=Y_{k}+X_{k-1}}$

Using ${\displaystyle E(\cdot )}$ to denote expectation, we have:

${\displaystyle E(X_{k})=E(Y_{k})+E(X_{k-1})}$

But ${\displaystyle Y_{k}}$ is a geometric random variable with probability of success ${\displaystyle p=k/n}$. The expectation of a geometric random variable is

${\displaystyle 1/p=n/k}$.

Plugging this into the formula above and unrolling the recursion yields the same formula given in the previous section:

${\displaystyle E(X_{n})=n\sum _{k=1}^{n}{1 \over k}}$

## Input

1
2
3
4
5
10
20
30
31
32
33


## Output

1
3
1
5 -
2
1
8 -
3
5
11 --
12
73
29 ---
252
3704479
71 -------
3879876
65960897707
119 -----------
77636318760
1967151510157
124 -------------
2329089562800
3934303020314
129 -------------
4512611027925
4071048809039
134 -------------
4375865239200