Birthdays#1317

Birthdays (Editorial)

First, let's compute the probability $p (n)$ \overline{p(n)} that in a group of $n$ people all birthdays are distinct. If $n$ is greater than $365$ , then by the pigeonhole principle this probability is zero. If $n$ does not exceed $365$ , we reason as follows.

We choose the first person and note his birthday. Then we choose the second person: the probability that his birthday does not coinside with the first person's birthday is $1 - 1/365$ 1 - 1 / 365. For the third person, the probability that his birthday does not coinside with the birthdays of the first two people is $1 - 2/365$ 1 - 2 / 365.

Continuing this reasoning, for the last person the probability that their birthday does not coinside with the birthdays of all the previous ones is $1 - (n - 1) /365$ 1 - (n - 1) / 365.

Multiplying all these probabilities, we obtain the probability that all birthdays in the group are different:

p (n) = 1 \cdot (1 - \frac{1}{365}) \cdot (1 - \frac{2}{365}) \cdot ... \cdot (1 - \frac{n - 1}{365})

\overline{p(n)} = 1 \cdot \left(1 - \frac{1}{365}\right) \cdot \left(1 - \frac{2}{365}\right) \cdot ... \cdot \left(1 - \frac{n - 1}{365}\right)

Then, the probability that at least two people out of $n$ share the same birthday is equal to one minus the probability that all birthdays are distinct:

p (n) = 1 - p (n)

p(n) = 1 - \overline{p(n)}

Algorithm implementation

In the array $p [i]$ we’ll store the corresponding probability values $p (i)$ .

double p[401];

Let $p [1] = 1$ p[1] = 1. The remaining values of the array $p [i]$ are computed using the formula given in the problem analysis.

p[1] = 1.0;
for (i = 2; i < 401; i++)
  p[i] = p[i-1] * (1.0 - (i - 1.0) / 365);

For each input value $n$ , compute the corresponding probability and print the result.

while (scanf("%d",&n) == 1)
  printf("%.8lf%%\n",(1 - p[n]) * 100);