How many people must be there in a room to make the probability 100% that at-least two people in the room have same birthday?
Answer: 367 (since there are 366 possible birthdays, including February 29).
The above question was simple. Try the below question yourself.

How many people must be there in a room to make the probability 50% that at-least two people in the room have same birthday?
The number is surprisingly very low. In fact, we need only 70 people to make the probability 99.9 %.

Let us discuss the generalized formula.

What is the probability that two persons among n have same birthday?
Let the probability that two people in a room with n have same birthday be P(same). P(Same) can be easily evaluated in terms of P(different) where P(different) is the probability that all of them have different birthday.

P(same) = 1 – P(different)

P(different) can be written as 1 x (364/365) x (363/365) x (362/365) x …. x (1 – (n-1)/365)

How did we get the above expression?
Persons from first to last can get birthdays in following order for all birthdays to be distinct:
The first person can have any birthday among 365
The second person should have a birthday which is not same as first person
The third person should have a birthday which is not same as first two persons.
…………….
……………
The n’th person should have a birthday which is not same as any of the earlier considered (n-1) persons.

Approximation of above expression
The above expression can be approximated using Taylor’s Series. provides a first-order approximation for ex for x << 1: To apply this approximation to the first expression derived for p(different), set x = -a / 365. Thus, The above expression derived for p(different) can be written as
1 x (1 – 1/365) x (1 – 2/365) x (1 – 3/365) x …. x (1 – (n-1)/365)

By putting the value of 1 – a/365 as e-a/365, we get following.   Therefore,

p(same) = 1- p(different) An even coarser approximation is given by

p(same) By taking Log on both sides, we get the reverse formula. Using the above approximate formula, we can approximate number of people for a given probability. For example the following C++ function find() returns the smallest n for which the probability is greater than the given p.

Implementation of approximate formula.
The following is program to approximate number of people for a given probability.

## C++

 `// C++ program to approximate number of people in Birthday Paradox  ` `// problem ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `// Returns approximate number of people for a given probability ` `int` `find(``double` `p) ` `{ ` `    ``return` `ceil``(``sqrt``(2*365*``log``(1/(1-p)))); ` `} ` ` `  `int` `main() ` `{ ` `   ``cout << find(0.70); ` `} `

## Java

 `// Java program to approximate number ` `// of people in Birthday Paradox problem ` `class` `GFG { ` `     `  `    ``// Returns approximate number of people  ` `    ``// for a given probability ` `    ``static` `double` `find(``double` `p) { ` `         `  `        ``return` `Math.ceil(Math.sqrt(``2` `*  ` `            ``365` `* Math.log(``1` `/ (``1` `- p)))); ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `         `  `        ``System.out.println(find(``0.70``));  ` `    ``} ` `} ` ` `  `// This code is contributed by Anant Agarwal. `

## Python3

 `# Python3 code to approximate number ` `# of people in Birthday Paradox problem ` `import` `math ` ` `  `# Returns approximate number of  ` `# people for a given probability ` `def` `find( p ): ` `    ``return` `math.ceil(math.sqrt(``2` `*` `365` `*` `                     ``math.log(``1``/``(``1``-``p)))); ` ` `  `# Driver Code ` `print``(find(``0.70``)) ` ` `  `# This code is contributed by "Sharad_Bhardwaj". `

## C#

 `// C# program to approximate number ` `// of people in Birthday Paradox problem. ` `using` `System; ` ` `  `class` `GFG { ` `      `  `    ``// Returns approximate number of people  ` `    ``// for a given probability ` `    ``static` `double` `find(``double` `p) { ` `          `  `        ``return` `Math.Ceiling(Math.Sqrt(2 *  ` `            ``365 * Math.Log(1 / (1 - p)))); ` `    ``} ` `      `  `    ``// Driver code ` `    ``public` `static` `void` `Main()  ` `    ``{          ` `    ``Console.Write(find(0.70));  ` `    ``} ` `} ` `  `  `// This code is contributed by nitin mittal. `

## PHP

 ` `

Output :

`30`

Applications:
1) Birthday Paradox is generally discussed with hashing to show importance of collision handling even for a small set of keys.
2) Birthday Attack

## tags:

Mathematical Randomized Mathematical