I finally solved the Birthday Problem using Java

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++)
{
}
return abd;
}

}


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 )  );

• 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.) – 410_Gone Jun 30 '17 at 19:16
• I see your point. I was just trying to follow how npr is usually written in Mathematics. Which is n! / (n-r)! – Joseph Kreifels II Jun 30 '17 at 19:47
• 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. – rossum Jun 30 '17 at 20:51

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;
}

• 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 – Joseph Kreifels II Jun 30 '17 at 20:34