VLSI DV Interview Puzzles · All levels

Birthday Collision Threshold

How many people are needed so that probability of at least one shared birthday exceeds 50%? Ignore leap years and assume uniform birthdays.

Puzzle

Difficulty: Medium · Puzzle 5 of 6 · Topic: Probability Puzzles

How many people are needed so that probability of at least one shared birthday exceeds 50%? Ignore leap years and assume uniform birthdays.

Hint

Compute complement first: all birthdays distinct.

Step-by-step solution

diagram

1) For n people, P(no match) = product_{k=0 to n-1} (365-k)/365.
2) P(at least one match) = 1 - P(no match).
3) Evaluate around n=23: P(no match) approx 0.4927.
4) So P(match) approx 1 - 0.4927 = 0.5073.
5) At n=22 this value is still below 0.5, so threshold is 23.

Answer

Answer: 23 people are needed for probability > 50% of a shared birthday.

Why candidates get it wrong

Linear intuition ('365/2') ignores pairwise combinations growing as n(n-1)/2.

Interviewer follow-up

Approximate n for 99% collision probability.

Navigate