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

}

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.) — Der Kommissar
– Der Kommissar, Commented Jun 30, 2017 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
– Joseph Kreifels II, Commented Jun 30, 2017 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
– rossum, Commented Jun 30, 2017 at 20:51

JS1 · Accepted Answer · 2017-06-30 20:38:37Z

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
– Joseph Kreifels II, Commented Jun 30, 2017 at 20:34

Stack Exchange Network

I finally solved the Birthday Problem using Java

1 Answer 1

Can be done without BigDecimals and factorials

Factorial function was strange

You must log in to answer this question.

Hot Network Questions

I finally solved the Birthday Problem using Java

1 Answer 1

Can be done without BigDecimals and factorials

Factorial function was strange

You must log in to answer this question.

Related

Hot Network Questions