Tuesday, October 20, 2015

BirthdayOdds

Problem:

TopCoder Problem Statement - BirthdayOdds
Single Round Match 174 Round 1 - Division I, Level One
Single Round Match 174 Round 1 - Division II, Level Two

Overview:

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.

Java Source:
     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 }
Notes:

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