# Probability of getting at least K heads in N tosses of Coins

Given N number of coins, the task is to find probability of getting at least K number of heads after tossing all the N coins simultaneously.

Example :

```Suppose we have 3 unbiased coins and we have to
find the probability of getting at least 2 heads,
so there are 23 = 8 ways to toss these
coins, i.e.,
HHH, HHT, HTH, HTT, THH, THT, TTH, TTT

Out of which there are 4 set which contain at
least 2 Heads i.e.,
HHH, HHT, HH, THH

So the probability is 4/8 or 0.5
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The probability of exactly k success in n trials with probability p of success in any trial is given by:

So Probability ( getting at least 4 heads )=

Method 1 (Naive)
A Naive approach is to store the value of factorial in dp[] array and call it directly whenever it is required. But the problem of this approach is that we can only able to store it up to certain value, after that it will lead to overflow.

Below is the implementation of above approach

## C++

 `// Naive approach in C++ to find probability of ` `// at least k heads ` `#include ` `using` `namespace` `std; ` `#define MAX 21 ` ` `  `double` `fact[MAX]; ` ` `  `// Returns probability of getting at least k ` `// heads in n tosses. ` `double` `probability(``int` `k, ``int` `n) ` `{ ` `    ``double` `ans = 0; ` `    ``for` `(``int` `i = k; i <= n; ++i) ` ` `  `        ``// Probability of getting exactly i ` `        ``// heads out of n heads ` `        ``ans += fact[n] / (fact[i] * fact[n - i]); ` ` `  `    ``// Note: 1 << n = pow(2, n) ` `    ``ans = ans / (1LL << n); ` `    ``return` `ans; ` `} ` ` `  `void` `precompute() ` `{ ` `    ``// Preprocess all factorial only upto 19, ` `    ``// as after that it will overflow ` `    ``fact[0] = fact[1] = 1; ` ` `  `    ``for` `(``int` `i = 2; i < 20; ++i) ` `        ``fact[i] = fact[i - 1] * i; ` `} ` ` `  `// Drive code ` `int` `main() ` `{ ` `    ``precompute(); ` ` `  `    ``// Probability of getting 2 head out of 3 coins ` `    ``cout << probability(2, 3) << ````" "````; ` ` `  `    ``// Probability of getting 3 head out of 6 coins ` `    ``cout << probability(3, 6) <<````" "````; ` ` `  `    ``// Probability of getting 12 head out of 18 coins ` `    ``cout << probability(12, 18); ` ` `  `    ``return` `0; ` `} `

## Java

 `// JAVA Code for Probability of getting  ` `// atleast K heads in N tosses of Coins ` `class` `GFG { ` `     `  `    ``public` `static` `double` `fact[]; ` `      `  `    ``// Returns probability of getting at least k ` `    ``// heads in n tosses. ` `    ``public` `static` `double` `probability(``int` `k, ``int` `n) ` `    ``{ ` `        ``double` `ans = ``0``; ` `        ``for` `(``int` `i = k; i <= n; ++ i) ` `      `  `            ``// Probability of getting exactly i ` `            ``// heads out of n heads ` `            ``ans += fact[n] / (fact[i] * fact[n-i]); ` `      `  `        ``// Note: 1 << n = pow(2, n) ` `        ``ans = ans / (``1` `<< n); ` `        ``return` `ans; ` `    ``} ` `      `  `    ``public` `static` `void` `precompute() ` `    ``{ ` `        ``// Preprocess all factorial only upto 19, ` `        ``// as after that it will overflow ` `        ``fact[``0``] = fact[``1``] = ``1``; ` `      `  `        ``for` `(``int` `i = ``2``; i < ``20``; ++i) ` `            ``fact[i] = fact[i - ``1``] * i; ` `    ``} ` `      `  `    ``// Drive code ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``fact = ``new` `double``[``100``]; ` `        ``precompute(); ` `      `  `        ``// Probability of getting 2 head out ` `        ``// of 3 coins ` `        ``System.out.println(probability(``2``, ``3``)); ` `      `  `        ``// Probability of getting 3 head out ` `        ``// of 6 coins ` `        ``System.out.println(probability(``3``, ``6``)); ` `      `  `        ``// Probability of getting 12 head out ` `        ``// of 18 coins ` `        ``System.out.println(probability(``12``, ``18``)); ` `      `  `    ``} ` ` ``} ` `// This code is contributed by Arnav Kr. Mandal `

## Python3

 `# Naive approach in Python3  ` `# to find probability of ` `# at least k heads ` ` `  `MAX``=``21` ` `  `fact``=``[``0``]``*``MAX` ` `  `# Returns probability of  ` `# getting at least k ` `# heads in n tosses. ` `def` `probability(k, n): ` `    ``ans ``=` `0` `    ``for` `i ``in` `range``(k,n``+``1``): ` ` `  `        ``# Probability of getting exactly i ` `        ``# heads out of n heads ` `        ``ans ``+``=` `fact[n] ``/` `(fact[i] ``*` `fact[n ``-` `i]) ` ` `  `    ``# Note: 1 << n = pow(2, n) ` `    ``ans ``=` `ans ``/` `(``1` `<< n) ` `    ``return` `ans ` ` `  `def` `precompute(): ` `     `  `    ``# Preprocess all factorial  ` `    ``# only upto 19, ` `    ``# as after that it  ` `    ``# will overflow ` `    ``fact[``0``] ``=` `1` `    ``fact[``1``] ``=` `1` ` `  `    ``for` `i ``in` `range``(``2``,``20``): ` `        ``fact[i] ``=` `fact[i ``-` `1``] ``*` `i ` ` `  `# Driver code ` `if` `__name__``=``=``'__main__'``: ` `    ``precompute() ` ` `  `    ``# Probability of getting 2  ` `    ``# head out of 3 coins ` `    ``print``(probability(``2``, ``3``)) ` ` `  `    ``# Probability of getting  ` `    ``# 3 head out of 6 coins ` `    ``print``(probability(``3``, ``6``)) ` ` `  `    ``# Probability of getting  ` `    ``# 12 head out of 18 coins ` `    ``print``(probability(``12``, ``18``)) ` `     `  `# This code is contributed by  ` `# mits `

## C#

 `// C# Code for Probability of getting  ` `// atleast K heads in N tosses of Coins ` `using` `System; ` ` `  `class` `GFG  ` `{ ` `     `  `    ``public` `static` `double` `[]fact; ` `     `  `    ``// Returns probability of getting at least k ` `    ``// heads in n tosses. ` `    ``public` `static` `double` `probability(``int` `k, ``int` `n) ` `    ``{ ` `        ``double` `ans = 0; ` `        ``for` `(``int` `i = k; i <= n; ++ i) ` `     `  `            ``// Probability of getting exactly i ` `            ``// heads out of n heads ` `            ``ans += fact[n] / (fact[i] * fact[n - i]); ` `     `  `        ``// Note: 1 << n = pow(2, n) ` `        ``ans = ans / (1 << n); ` `        ``return` `ans; ` `    ``} ` `     `  `    ``public` `static` `void` `precompute() ` `    ``{ ` `        ``// Preprocess all factorial only upto 19, ` `        ``// as after that it will overflow ` `        ``fact[0] = fact[1] = 1; ` `     `  `        ``for` `(``int` `i = 2; i < 20; ++i) ` `            ``fact[i] = fact[i - 1] * i; ` `    ``} ` `     `  `    ``// Drive code ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `        ``fact = ``new` `double``[100]; ` `        ``precompute(); ` `     `  `        ``// Probability of getting 2 head out ` `        ``// of 3 coins ` `        ``Console.WriteLine(probability(2, 3)); ` `     `  `        ``// Probability of getting 3 head out ` `        ``// of 6 coins ` `        ``Console.WriteLine(probability(3, 6)); ` `     `  `        ``// Probability of getting 12 head out ` `        ``// of 18 coins ` `        ``Console.Write(probability(12, 18)); ` `     `  `    ``} ` `} ` `// This code is contributed by nitin mittal. `

## PHP

 ` `

Output:

```0.5
0.65625
0.118942
```

Time Complexity: O(n) where n < 20
Auxiliary space: O(n)

Method 2 (Dynamic Programming and Log)
Another way is to use Dynamic programming and logarithm. log() is indeed useful to store the factorial of any number without worrying about overflow. Let’s see how we use it:

```At first let see how n! can be written.
n! = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1

Now take log on base 2 both the sides as:
=> log(n!) = log(n) + log(n-1) + log(n-2) + ... + log(3)
+ log(2) + log(1)

Now whenever we need to find the factorial of any number, we can use
this precomputed value. For example:
Suppose if we want to find the value of nCi which can be written as:
=> nCi = n! / (i! * (n-i)! )

Taking log2() both sides as:
=> log2 (nCi) = log2 ( n! / (i! * (n-i)! ) )
=> log2 (nCi) = log2 ( n! ) - log2(i!) - log2( (n-i)! )  `

Putting dp[num] = log2 (num!), we get:
=> log2 (nCi) = dp[n] - dp[i] - dp[n-i]

But as we see in above relation there is an extra factor of 2n which
tells the probability of getting i heads, so
=> log2 (2n) = n.

We will subtract this n from above result to get the final answer:
=> Pi (log2 (nCi)) = dp[n] - dp[i] - dp[n-i] - n

Now: Pi (nCi) = 2 dp[n] - dp[i] - dp[n-i] - n

Tada! Now the questions boils down the summation of Pi for all i in
[k, n] will yield the answer which can be calculated easily without
overflow.
```

Below are the codes to illustrate this:

## C++

 `// Dynamic and Logarithm approach find probability of ` `// at least k heads ` `#include ` `using` `namespace` `std; ` `#define MAX 100001 ` ` `  `// dp[i] is going to store Log ( i !) in base 2 ` `double` `dp[MAX]; ` ` `  `double` `probability(``int` `k, ``int` `n) ` `{ ` `    ``double` `ans = 0; ``// Initialize result ` ` `  `    ``// Iterate from k heads to n heads ` `    ``for` `(``int` `i=k; i <= n; ++i) ` `    ``{ ` `        ``double` `res = dp[n] - dp[i] - dp[n-i] - n; ` `        ``ans += ``pow``(2.0, res); ` `    ``} ` ` `  `    ``return` `ans; ` `} ` ` `  `void` `precompute() ` `{ ` `    ``// Preprocess all the logarithm value on base 2 ` `    ``for` `(``int` `i=2; i < MAX; ++i) ` `        ``dp[i] = log2(i) + dp[i-1]; ` `} ` ` `  `// Drive code ` `int` `main() ` `{ ` `    ``precompute(); ` ` `  `    ``// Probability of getting 2 head out of 3 coins ` `    ``cout << probability(2, 3) << ````" "````; ` ` `  `    ``// Probability of getting 3 head out of 6 coins ` `    ``cout << probability(3, 6) << ````" "````; ` ` `  `    ``// Probability of getting 500 head out of 10000 coins ` `    ``cout << probability(500, 1000); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Dynamic and Logarithm approach find probability of ` `// at least k heads ` `import` `java.math.*; ` `class` `GFG { ` `     `  `static` `int` `MAX = ``100001``; ` ` `  `// dp[i] is going to store Log ( i !) in base 2 ` `static` `double` `dp[] = ``new` `double``[MAX]; ` ` `  `static` `double` `probability(``int` `k, ``int` `n) ` `{ ` `    ``double` `ans = ``0.0``; ``// Initialize result ` ` `  `    ``// Iterate from k heads to n heads ` `    ``for` `(``int` `i=k; i <= n; ++i) ` `    ``{ ` `        ``double` `res = dp[n] - dp[i] - dp[n-i] - n; ` `        ``ans += Math.pow(``2.0``, res); ` `    ``} ` ` `  `    ``return` `ans; ` `} ` ` `  `static` `void` `precompute() ` `{ ` `    ``// Preprocess all the logarithm value on base 2 ` `    ``for` `(``int` `i=``2``; i < MAX; ++i) ` `        ``dp[i] = (Math.log(i)/Math.log(``2``)) + dp[i-``1``]; ` `} ` ` `  `// Drive code ` `public` `static` `void` `main(String args[]) ` `{ ` `    ``precompute(); ` ` `  `    ``// Probability of getting 2 head out of 3 coins ` `    ``System.out.println(probability(``2``, ``3``)); ` ` `  `    ``// Probability of getting 3 head out of 6 coins ` `    ``System.out.println(probability(``3``, ``6``)); ` ` `  `    ``// Probability of getting 500 head out of 10000 coins ` `    ``System.out.println(probability(``500``, ``1000``)); ` `} ` ` `  `} `

## Python3

 `# Dynamic and Logarithm approach find probability of  ` `# at least k heads ` ` `  `from` `math ``import` `log2 ` `MAX``=``100001` ` `  `# dp[i] is going to store Log ( i !) in base 2  ` `dp``=``[``0``]``*``MAX` ` `  `def` `probability( k, n):  ` ` `  `    ``ans ``=` `0` `# Initialize result  ` ` `  `    ``# Iterate from k heads to n heads  ` `    ``for` `i ``in` `range``(k,n``+``1``): ` ` `  `        ``res ``=` `dp[n] ``-` `dp[i] ``-` `dp[n``-``i] ``-` `n  ` `        ``ans ``=` `ans ``+` `pow``(``2.0``, res)  ` `     `  ` `  `    ``return` `ans  ` ` `  ` `  `def` `precompute():  ` ` `  `    ``# Preprocess all the logarithm value on base 2  ` `    ``for` `i ``in` `range``(``2``,``MAX``):  ` `        ``dp[i] ``=` `log2(i) ``+` `dp[i``-``1``]  ` ` `  ` `  `# Drive code  ` `if` `__name__``=``=``'__main__'``: ` `    ``precompute()  ` ` `  `    ``# Probability of getting 2 head out of 3 coins  ` `    ``print``(probability(``2``, ``3``))  ` ` `  `    ``# Probability of getting 3 head out of 6 coins  ` `    ``print``(probability(``3``, ``6``))  ` ` `  `    ``# Probability of getting 500 head out of 10000 coins  ` `    ``print``(probability(``500``, ``1000``)) ` ` `  `#this code is contributed by ash264 `

## C#

 `// Dynamic and Logarithm approach find probability of  ` `// at least k heads  ` `using` `System; ` ` `  `class` `GFG  ` `{  ` `     `  `static` `int` `MAX = 100001;  ` ` `  `// dp[i] is going to store Log ( i !) in base 2  ` `static` `double``[] dp = ``new` `double``[MAX];  ` ` `  `static` `double` `probability(``int` `k, ``int` `n)  ` `{  ` `    ``double` `ans = 0.0; ``// Initialize result  ` ` `  `    ``// Iterate from k heads to n heads  ` `    ``for` `(``int` `i = k; i <= n; ++i)  ` `    ``{  ` `        ``double` `res = dp[n] - dp[i] - dp[n-i] - n;  ` `        ``ans += Math.Pow(2.0, res);  ` `    ``}  ` `    ``return` `ans;  ` `}  ` ` `  `static` `void` `precompute()  ` `{  ` `    ``// Preprocess all the logarithm value on base 2  ` `    ``for` `(``int` `i = 2; i < MAX; ++i)  ` `        ``dp[i] = (Math.Log(i) / Math.Log(2)) + dp[i - 1];  ` `}  ` ` `  `// Drive code  ` `public` `static` `void` `Main()  ` `{  ` `    ``precompute();  ` ` `  `    ``// Probability of getting 2 head out of 3 coins  ` `    ``Console.WriteLine(probability(2, 3));  ` ` `  `    ``// Probability of getting 3 head out of 6 coins  ` `    ``Console.WriteLine(probability(3, 6));  ` ` `  `    ``// Probability of getting 500 head out of 10000 coins  ` `    ``Console.WriteLine(Math.Round(probability(500, 1000),6));  ` `}  ` `}  ` ` `  `// This code is contributed by mits `

## PHP

 ` `

Output:

```0.5
0.65625
0.512613
```

Time Complexity: O(n)
Auxiliary space: O(n)

This approach is beneficial for large value of n ranging from 1 to 106

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

code

load comments