How many random packs do you expect to buy to complete a 50-sticker collection?

seniornice to knowfreq 22%

answer

count the waits, not the whole total
split at each new sticker
one over the success probability
the harmonic sum appears

basics

~20 s

About 225 packs, if each pack holds one sticker drawn uniformly at random. Split the hunt into 50 stages with expected lengths 50/50, 50/49, ..., 50/1, which sum to 50 times the 50th harmonic number.

solid answer

~50 s

Model each pack as one sticker drawn uniformly and independently from the 50 kinds. Break the purchase into stages: stage k runs from the moment you hold k distinct stickers until you get the (k+1)th. During that stage each pack is new with probability (50-k)/50, so the number of packs you wait is geometric and its expected length is 50/(50-k). The total is the sum of these waits, and linearity of expectation adds them even though the stage lengths are random. So E[T] = 50/50 + 50/49 + ... + 50/1 = 50 * (1 + 1/2 + ... + 1/50), which is 50 times the harmonic number H_50 of about 4.499, giving roughly 225 packs. The distribution is right-skewed, so the median is lower and the tail is long. The last sticker alone costs 50 expected packs, about a fifth of the whole job.

Model each pack as one sticker drawn uniformly and independently from the 50 kinds. Break the purchase into stages: stage k runs from the moment you hold k distinct stickers until you get the (k+1)th. During that stage each pack is new with probability `(50-k)/50`, so the number of packs you wait is geometric and its expected length is `50/(50-k)`. The total is the sum of these waits, and linearity of expectation adds them even though the stage lengths are random. So `E[T] = 50/50 + 50/49 + ... + 50/1 = 50 * (1 + 1/2 + ... + 1/50)`, which is 50 times the harmonic number `H_50` of about 4.499, giving roughly 225 packs. The distribution is right-skewed, so the median is lower and the tail is long. The last sticker alone costs 50 expected packs, about a fifth of the whole job.

code

python · 16 lines

python

import random

def packs_to_complete(n=50):
    seen = set()
    packs = 0
    while len(seen) < n:
        seen.add(random.randrange(n))
        packs += 1
    return packs

trials = 20000
simulated = sum(packs_to_complete() for _ in range(trials)) / trials
exact = 50 * sum(1 / k for k in range(1, 51))

print(round(simulated, 1))  # about 225
print(round(exact, 1))      # 225.0

go deeper

for a junior

Recall that a wait for an event of probability p has expected length 1/p, and that duplicates make the total far larger than the number of kinds.

for a middle

Set up the stage decomposition, identify each stage as a geometric wait, and add the means to reach 50 times the harmonic number without assuming independence between stages.

for a senior

Go past the mean: explain where the cost concentrates, how the total scales with collection size, and why a right-skewed total makes a budget based on the expectation insufficient.

for a principal

Own the modelling assumptions and their consequences: uniform rarity, independent packs and no trading are choices, and each one materially changes the number you would put in front of a decision maker.

The setup

Each pack contains one sticker. The sticker is drawn uniformly at random from 50 kinds, independently of every other pack, and duplicates are possible. How many packs until you hold all 50?

This is the coupon collector problem. Its value in an interview is that it looks like it needs the distribution of a complicated total, and it does not: it needs a decomposition plus linearity of expectation.

Stages and geometric waits

Let T be the total number of packs, and split it by milestone. Write T = T_0 + T_1 + ... + T_49, where T_k is the number of packs bought while you hold exactly k distinct stickers, ending with the pack that takes you to k+1.

While you hold k distinct stickers, 50 - k kinds are still missing, so any given pack is new with probability

p_k = (50 - k)/50

Each pack is an independent trial with that success probability, so T_k follows a geometric distribution counting trials up to and including the first success. Its expectation is 1/p_k = 50/(50 - k).

Adding the stages

The stage lengths are random and the stages are not interchangeable, but expectation of a sum is the sum of expectations regardless, so

E[T] = sum over k = 0 to 49 of 50/(50 - k) = 50/50 + 50/49 + 50/48 + ... + 50/1

Factor out the 50 and reverse the order of the terms:

E[T] = 50 * (1 + 1/2 + 1/3 + ... + 1/50) = 50 * H_50

where H_n is the nth harmonic number. Since H_50 is about 4.499, the answer is about 225 packs.

Where the cost sits

Read the terms from the other end and the structure becomes obvious. The first sticker costs 1 pack: anything is new. The second costs 50/49, barely more than 1. Halfway in, the 25th costs about 2. The 49th costs 25, and the last one costs 50 packs on its own, roughly 22 percent of the entire expected total. The tail of the collection is where the money goes, and that is the intuition the question is really testing: completion cost is dominated by the final few items, not spread evenly.

Scaling

For n kinds the same argument gives E[T] = n * H_n, and since H_n is approximately ln(n) + 0.5772 + 1/(2n), the expected total is about

n*ln(n) + 0.5772*n + 0.5

Growth is a little faster than linear in n. Doubling the collection to 100 kinds gives about 519 packs, more than twice 225, because both the number of stages and the cost of the late stages increase.

Spread, not just the mean

The mean is only half the story. The total is right-skewed, and its concentration is worth knowing: the probability of still missing at least one kind after n*ln(n) + c*n packs decays roughly like e^(-c). So buying about 225 packs leaves you a substantial chance of still being short, while buying around 400 makes completion very likely. Quoting a mean without noting the skew is the weak version of the answer; an interviewer will often follow up with "and how many packs to be 95 percent sure?" precisely to see whether you distinguish an expectation from a high quantile.

Assumptions worth naming out loud

The clean answer depends on three modelling assumptions, and stating them is part of a strong response:

Uniform rarity. If some stickers are deliberately rarer, the expectation strictly increases; the uniform case is the cheapest. There is no simple closed form for the general case.
Independence between packs. Real packs are often filled without replacement within a pack or balanced across a print run, which changes the answer.
No trading. Exchanging duplicates changes the problem entirely, which is exactly why collectors trade.

An interviewer who asks this is usually testing three things: whether you decompose a total into stages instead of attacking it whole, whether you know the mean of a geometric wait is one over its success probability, and whether you use linearity of expectation without pausing to worry about how the stages relate to each other.

## The setup Each pack contains one sticker. The sticker is drawn uniformly at random from 50 kinds, independently of every other pack, and duplicates are possible. How many packs until you hold all 50? This is the coupon collector problem. Its value in an interview is that it looks like it needs the distribution of a complicated total, and it does not: it needs a decomposition plus linearity of expectation. ## Stages and geometric waits Let T be the total number of packs, and split it by milestone. Write `T = T_0 + T_1 + ... + T_49`, where `T_k` is the number of packs bought while you hold exactly k distinct stickers, ending with the pack that takes you to k+1. While you hold k distinct stickers, `50 - k` kinds are still missing, so any given pack is new with probability `p_k = (50 - k)/50` Each pack is an independent trial with that success probability, so `T_k` follows a geometric distribution counting trials up to and including the first success. Its expectation is `1/p_k = 50/(50 - k)`. ## Adding the stages The stage lengths are random and the stages are not interchangeable, but expectation of a sum is the sum of expectations regardless, so `E[T] = sum over k = 0 to 49 of 50/(50 - k) = 50/50 + 50/49 + 50/48 + ... + 50/1` Factor out the 50 and reverse the order of the terms: `E[T] = 50 * (1 + 1/2 + 1/3 + ... + 1/50) = 50 * H_50` where `H_n` is the nth harmonic number. Since `H_50` is about 4.499, the answer is about 225 packs. ## Where the cost sits Read the terms from the other end and the structure becomes obvious. The first sticker costs 1 pack: anything is new. The second costs `50/49`, barely more than 1. Halfway in, the 25th costs about 2. The 49th costs 25, and the last one costs 50 packs on its own, roughly 22 percent of the entire expected total. The tail of the collection is where the money goes, and that is the intuition the question is really testing: completion cost is dominated by the final few items, not spread evenly. ## Scaling For n kinds the same argument gives `E[T] = n * H_n`, and since `H_n` is approximately `ln(n) + 0.5772 + 1/(2n)`, the expected total is about `n*ln(n) + 0.5772*n + 0.5` Growth is a little faster than linear in n. Doubling the collection to 100 kinds gives about 519 packs, more than twice 225, because both the number of stages and the cost of the late stages increase. ## Spread, not just the mean The mean is only half the story. The total is right-skewed, and its concentration is worth knowing: the probability of still missing at least one kind after `n*ln(n) + c*n` packs decays roughly like `e^(-c)`. So buying about 225 packs leaves you a substantial chance of still being short, while buying around 400 makes completion very likely. Quoting a mean without noting the skew is the weak version of the answer; an interviewer will often follow up with "and how many packs to be 95 percent sure?" precisely to see whether you distinguish an expectation from a high quantile. ## Assumptions worth naming out loud The clean answer depends on three modelling assumptions, and stating them is part of a strong response: - **Uniform rarity.** If some stickers are deliberately rarer, the expectation strictly increases; the uniform case is the cheapest. There is no simple closed form for the general case. - **Independence between packs.** Real packs are often filled without replacement within a pack or balanced across a print run, which changes the answer. - **No trading.** Exchanging duplicates changes the problem entirely, which is exactly why collectors trade. An interviewer who asks this is usually testing three things: whether you decompose a total into stages instead of attacking it whole, whether you know the mean of a geometric wait is one over its success probability, and whether you use linearity of expectation without pausing to worry about how the stages relate to each other.

Why is the final sticker so expensive relative to the rest?
When 49 of 50 kinds are already held, each pack is new with probability 1/50, so the expected wait for that last one is 50 packs, about 22 percent of the roughly 225 total. Completion cost concentrates in the tail: the last handful of items dominate, while the first half of the collection arrives almost for free.
How does the expected total scale with the number of kinds n?
It is `n * H_n`, which is approximately `n*ln(n) + 0.5772*n + 0.5`, so growth is slightly faster than linear. Going from 50 kinds to 100 raises the expectation from about 225 to about 519, more than doubling, because both the number of stages and the length of the late stages grow.
What changes if some stickers are printed rarer than others?
The expected number of packs strictly increases; uniform rarity is the cheapest case. There is no tidy closed form in general, and the answer becomes dominated by the rarest kind, whose expected wait alone is one over its probability. This is why deliberately skewed print runs make completion far more expensive than the uniform calculation suggests.
How many packs would you need to be reasonably confident of completing the set, rather than merely expecting to?
Considerably more than the mean, because the total is right-skewed. The chance of still missing a kind after `n*ln(n) + c*n` packs falls off roughly like `e^(-c)`, so pushing the budget a few multiples of n above the mean turns a coin-flip into near-certainty. Around 400 packs is a far safer target than 225.

Filling a bingo card gets harder as it fills: early daubs are almost automatic, and the final empty square is the one you sit and wait for.

saying these in an interview costs you the question

Answers 50 packs, ignoring duplicates entirely
Tries to derive the full distribution of the total before taking a mean
Worries that the stage lengths must be independent to add their means
Uses the probability of a new sticker instead of its reciprocal as the wait
Treats the expected total as the number needed to be confident of completing

How many random packs do you expect to buy to complete a 50-sticker collection?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

The setup

Stages and geometric waits

Adding the stages

Where the cost sits

Scaling

Spread, not just the mean

Assumptions worth naming out loud

▾common follow-ups4 questions

▾analogy~10 s

▾red flags5 flags

§ context

▾related questions6 questions

▾related topics3 topics

The setup

Stages and geometric waits

Adding the stages

Where the cost sits

Scaling

Spread, not just the mean

Assumptions worth naming out loud

answer

go deeper

context