TopCoder Problem Statement - BirthdayOdds |

Single Round Match 174 Round 1 - Division I, Level One |

Single Round Match 174 Round 1 - Division II, Level Two |

Calculate the mininum number of people required to assure that the probability of two people sharing a birthday meets the given threshold. The number of days in a year may vary.

1 2 3 public class BirthdayOdds { 4 5 public int minPeople(int minOdds, int daysInYear) { 6 7 double pA = 1.0; 8 double days = (double) daysInYear; 9 double cutOff = 1.0 - (minOdds / 100.0); 10 11 int numPeople = 1; 12 13 while (pA > cutOff) { 14 pA *= ((double) (daysInYear - numPeople) / days); 15 numPeople++; 16 } 17 18 return numPeople; 19 20 } 21 }

For a detailed discussion of the Birthday Problem, see the wikipedia entry here. This solution is based on the formula given in the "Calculating the probability" section.

Essentially we're calculating the probability that there is **not** a match, and then adding more
and more people thus reducing that probability until a certain threshold is met. That threshold
is (1 - minOdds) since we're calculating the probability of not matching whereas minOdds is the
probability of a match.

pA begins at 1 (i.e. daysInYear / daysInYear), then is multiplied by (daysInYear - 1 / daysInYear), (daysInYear - 2 / daysInYear), (daysInYear - 3 / daysInYear), ... With each multiplication pA gets smaller until it falls under the cutoff.

## No comments:

## Post a Comment