I finally solved the Birthday Problem using Java

Question

I like to put ideas and mathematics into code whenever I am interested in the subject. Ever since I was introduced to The Birthday Problem I wanted to throw it into a Java program.

I started writing the program in several different ways, all of which in the end would return "Infinite" for one of the variables dealing with the factorial numbers.

I finally stumbled across "BigInteger" and "BigDecimal", I was annoyed at first of how hard it was to use them, but I stuck with it.

Others have built similar programs that generate random dates and run x amount of times ( like 1000) to find an average percentage rate at with birthdays collide, mine finds the mathematical statistic.

Check this out, how cool is this?

//Author: Joseph Kreifels II
// Date: June 30, 2017
// Purpose: To find that percentage at which 2 students share a birthday.
import java.io.*;
import java.util.*;
import java.lang.Math;
import java.math.BigDecimal;
import java.math.RoundingMode;
public class Testing {
 public static void main(String[] args) {
 int n, r, i;
 double d;
 BigDecimal abd = new BigDecimal("0");
 Scanner sc = new Scanner(System.in);
 System.out.print("Enter Number of Students: ");
 i = sc.nextInt();
 n = 365;
 System.out.printf("Value of n: %d\n",n); 
 r = 365 - i;
 System.out.printf("Value of r: %d\n",r); 
 System.out.println("");
 System.out.println("Factorial of n = " + fact(n) );
 System.out.println("Factorial of r = " + fact(r) );
 // First get the NPR
 abd = fact(n).divide(fact(n-(n-r))) ;
 // Display NPR for FUN.
 System.out.println("NPR of n and (n-r) = " + abd);
 // Now we must divide it by x^y.. (e.g 365^5)
 abd = abd.divide(BigDecimal.valueOf( Math.pow(n,i) ),4, RoundingMode.HALF_UP);
 // I am lazy, So I turned it into a double to make the last 2 display statements easier to write.
 d = abd.doubleValue();
 System.out.printf("\nNot Same Birthday chance: %.0f%%\n", (d * 100) );
 System.out.printf("Same Birthday chance: %.0f%%\n", ((1 - d) * 100) );
 } // main
 public static BigDecimal fact(int num)
 {
 BigDecimal abd = new BigDecimal("1");
 int i;
 for(i=0; i<num; i++)
 {
 abd = abd.add(abd.multiply(BigDecimal.valueOf(i)));
 }
 return abd;
 }
}

enter image description here

EDIT: I feel like the results could come out better. So Here are some changes.

Now 4 Decimal Places

abd = abd.divide(BigDecimal.valueOf( Math.pow(n,i) ),4, RoundingMode.HALF_UP);

Now outputs a percentage with 2 decimal places (e.g. 25.65%)

 System.out.printf("\nNot Same Birthday chance: %.2f\n", (d * 100 ) );
 System.out.printf("Same Birthday chance: %.2f\n", ((1 - d) * 100 ) );

• Der Kommissar: Why n - (n - r) and not just r? You do an excessive amount of subtraction there. (If you factor n - (n - r) out, it becomes n - n + r = r.)
• Joseph Kreifels II: I see your point. I was just trying to follow how npr is usually written in Mathematics. Which is n! / (n-r)!
• rossum: It does not feature in the classical description of the problem, but the average year has close to 365.25 days in the Gregorian calendar.

Answer 1

Can be done without BigDecimals and factorials

You can compute the chance of shared birthdays using a simpler method, which avoids big numbers and factorials. With one person, the chance of all people having different birthdays is 100% (obviously). If you add a second person, that person has a 364/365 chance of also having a distinct birthday. When you add a third person, that person has a 363/365 chance of having a birthday distinct from the previous two. So as you keep adding more people, you keep track of the total chance of everyone having a distinct birthday by multiplying your current chance by (365-i)/365 for each new person.

Here is how you could do this in java:

import java.util.Scanner;
public class Testing {
 public static void main(String[] args)
 {
 Scanner sc = new Scanner(System.in);
 System.out.print("Enter Number of Students: ");
 int num = sc.nextInt();
 double notSameChance = 1.0;
 for (int i = 0; i < num; i++)
 notSameChance *= (365-i) / 365.0;
 System.out.printf("\nNot Same Birthday chance: %.0f%%\n",
 (notSameChance * 100) );
 System.out.printf("Same Birthday chance: %.0f%%\n",
 ((1 - notSameChance) * 100) );
 }
}

Factorial function was strange

Looking at your factorial function, it does an addition and a multiplication on every loop. Although it appears to work, you could make it simpler by doing just the multiplication, like this:

public static BigDecimal fact(int num)
{
 BigDecimal abd = new BigDecimal("1");
 for (int i=2; i<=num; i++) {
 abd = abd.multiply(BigDecimal.valueOf(i));
 }
 return abd;
}

• Joseph Kreifels II: Thanks for contributing. Looks a lot more cleaner. Nice to learn alternative ways to what I am doing. I was so focused on using factorials, I forgot that computers could do all the work, thus cancelling the need for factorials