Question

Birthday problem. Suppose that people enter a room one at a time. How 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:

• Choose a birthday for the next person, uniformly at random between 0 and n−1.n−1.
• Have that person enter the room.
• If that person shares a birthday with someone else in the room, stop; otherwise repeat.

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%.

Submission. Submit a .zip file containing DiscreteDistribution.java, ThueMorse.java, Birthday.java, and Minesweeper.java. You may not call library functions except those in the java.lang (such as Integer.parseInt() and Math.sqrt()). Use only Java features that have already been introduced in the course (e.g., loops and arrays, but not functions).

Answer 1

Solution :

Following is the fully commented code for the problem :

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in); //System.in is a standard input stream.
        System.out.println("Enter no. of days : ");
        int n= sc.nextInt(); //number of days
        System.out.println("Enter no. of trials : ");
        int trials = sc.nextInt();  //number of trials
        boolean[] birthdays = new boolean[n+2];
        int[] times = new int[n + 2]; //number of times i people entered the room
        int r;

        for (int t = 1; t <= trials; t++) {

            for (int k = 0; k < n; k++) { //reset birthday
                birthdays[k] = false;
            }

            for (int i = 1; i <=n; i++) { //number of times

                r = (int) (Math.random() * (n - 1)); //random birthday

                if (birthdays[r] == false) {
                    birthdays[r] = true;
                    continue;
                }

                else if (birthdays[r] == true) {
                    times[i]++; //number of times i people entered the room + 1
                    break;
                }

            }

        }
        int j = 1;
        //continue till the fraction reaches or exceeds 0.5
        while ((double) times[j] / trials <= 0.5) {
            System.out.print(j + "\t" + times[j] + "\t" + ((double) times[j] / trials));
            j++;
            System.out.println("");

        }
    }
}

Code demo :