// BirthdayProblem.java
// Written (mostly) in class on Tue 6-Oct-09

import java.util.Random;

public class BirthdayProblem {
  
  private static final Random random = new Random();
  
  // Place "people" people in a room, each with random
  // birthdays, and return true if there are any duplicate
  // birthdays.
  public static boolean doBirthdayTrial(int people) {
    boolean[] birthdaySeen = new boolean[365];
    for (int person=0; person<people; person++) {
      int birthday = random.nextInt(365);
      if (birthdaySeen[birthday] == true)
        return true;
      birthdaySeen[birthday] = true;
    }
    return false;
  }
  
  public static double birthdayOdds(int people, int trials) {
    int ok = 0;
    for (int trial=0; trial<trials; trial++) {
      if (doBirthdayTrial(people))
        ok++;
    }
    return 1.0 * ok / trials;
  }
  
  public static int birthdayProblem(int trials) {
    int people = 1;
    while (birthdayOdds(people, trials) < 0.5)
      people++;
    return people;
  }

  public static void main(String[] args) {
    int people = 21;
    int trials = 10000;
    System.out.println("Minimum number of people who must be in a room \n" +
                       "so it is more likely than not that at least two \n" +
                       "share a birthday is...");
    System.out.println(birthdayProblem(trials));
  }
}