Coursera - Computer Science: Programming With A Purpose

Week 3: Arrays - Birthday Problem

Suppose that people enter a room one at a time. How many people must enter until two share a birthday? Counterintuitively, after 23 people enter the room, there is approximately a 50–50 chance that two share a birthday. This phenomenon is known as the birthday problem or birthday paradox.

Write a program Birthday.java that takes two integer command-line arguments n and trials and performs the following experiment, trials times:

In each experiment, count the number of people that enter the room. Print a table that summarizes the results (the count i, the number of times that exactly i people enter the room, and the fraction of times that i or fewer people enter the room) for each possible value of i from 1 until the fraction reaches (or exceeds) 50%.

~/Desktop/arrays> java Birthday 365 1000000
1	0	0.0
2	2710	0.00271
3	5547	0.008257
4	8105	0.016362
5	10776	0.027138
6	13413	0.040551
7	15782	0.056333
8	17816	0.074149
9	20283	0.094432
10	22297	0.116729
11	24105	0.140834
12	26013	0.166847
13	27247	0.194094
14	28405	0.222499
15	29873	0.252372
16	30447	0.282819
17	31445	0.314264
18	31837	0.346101
19	32559	0.37866
20	32244	0.410904
21	32357	0.443261
22	32020	0.475281
23	31667	0.506948

~/Desktop/arrays> java Birthday 31 1000000
1	0	0.0
2	32270	0.03227
3	62580	0.09485
4	87582	0.182432
5	105596	0.288028
6	114427	0.402455
7	115494	0.517949

The birthday problem arises in many computer science applications, including hashing, cryptographic attacks, and testing random number generators.

Note: the above description is copied from Coursera and converted to markdown for convenience

Solution:

public class Birthday {

    public static void main(String[] args) {
        final int n = Integer.parseInt(args[0]);
        final int trials = Integer.parseInt(args[1]);

        // note: at most n+1 people will enter a room before encountering
        // a pair that shares the same birthday; hence need to try up to
        // n+1 instead of n
        final int[] count = new int[n+1];
        for (int t = 0; t < trials; t++) {
            final boolean[] seenBirthday = new boolean[n];
            for (int nextPerson = 0; nextPerson < count.length; nextPerson++) {
                int birthday = (int) (Math.random() * n);
                // check if any person in the room has the same birthday as the next person
                if (seenBirthday[birthday]) {
                    count[nextPerson]++;
                    break;
                }
                seenBirthday[birthday] = true;
            }
        }

        // compute fraction and output
        final double[] fraction = new double[count.length];
        System.out.println(1 + "\t" + count[0] + "\t" + fraction[0]);
        for (int i = 1; i < count.length; i++) {
            double sum = 0.0;
            for (int j = 1; j <= i; j++) {
                sum += count[j];
            }
            fraction[i] = sum / trials;
            System.out.println(i + 1 + "\t" + count[i] + "\t" + fraction[i]);
            if (fraction[i] >= 0.5) {
                break;
            }
        }
    }
}

Link To: Java Source Code