# Probability of getting more number of heads than tails if coins are tossed

Probability of Head Coins: Here, we are going to learn how to find the probability of getting more number of heads than tails if coins are tossed using dynamic programming approach? This is a very popular coding problem which has been featured in interview rounds of many big companies such as Paytm, Zomato, Amazon etc.
Submitted by Divyansh Jaipuriyar, on April 29, 2020

Problem statement:

Let N be a positive odd number. There are N coins, numbered 1, 2 , ... , N. For each i (1≤i≤N), when Coin i is tossed, it comes up heads with probability pi and tails with probability 1-pi.

Find the probability of having more heads than tails if coins are tossed.

Input:

The first line contains N, number of coins. The second line contains the probability of coming head in the coins.

Output:

Output the probability of having more number of heads than tails if coins are tossed.

Example with explanation:

```    Input:
N=3
[0.30, 0.60, 0.80]

Output:
0.612

is 0.3×0.6×0.8 = 0.144;

is 0.7×0.6×0.8 = 0.336;

is 0.3×0.4×0.8 = 0.096;

is 0.3×0.6×0.2 = 0.036

Thus, the probability of having more heads than tails is
0.144 + 0.336 + 0.096 + 0.036 = 0.612
```

Solution Approach

Dynamic Programming

Since the problem can be solved with recursion with time complexity of O(2^n) which is not accepted as there are other better approach to solve the problem with time complexity of O(n*n);

Let's assume prob[i][j] to be the probability of getting j heads with first i coins. To get j heads at the ith position, there are two possibilities:

If the number of heads till (i - 1) coins is equal to j then a tail comes at ith. If the number of heads till (i - 1) coins is equal to (j - 1) then a head comes at ith position.

The probability of occurring jth head at ith coin toss depends on the number of heads in (i-1)th coins, if (i-1) coin have (j-1) head then jth coin occurs at ith coin(p[i]), and if (i-1) coins have already j coins then at jth toss tails come(1-p[i]).

Pseudo Code:

```// p[] is the probability array,
// n is the size of array.
solve(p[],n):
// declare prob[n+1][n+1] array of having required head.
prob[n+1][n+1]

// no head out of 1 coins
prob=1-p

// one head out of one coins
prob=p

for(i=2;i<=n;i++)
// probability of having no heads.
prob[i]=prob[i-1]*(1-p[i])

for(i=2;i<=n;i++)
for(j=1;j<=i;j++)
prob[i][j]=prob[i-1][j-1]*p[i-1]+prob[i-1][j]*(1-p[i-1])
// probability of having jth head can take
// place in (i-1) coins or at (i)th coin.

sum=0
for(i=n/2+n%2;i<=n;i++)
sum+=prob[n][i]

return sum
```

Time complexity: In worst case O(n*n)

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

typedef double ll;

int main()
{
cout << "Enter number of test cases: ";
int t;
cin >> t;

while (t--) {
cout << "Enter the number of coins: ";
int n;
cin >> n;

ll p[n];

cout << "Enter the probabilities of head: ";
for (int i = 0; i < n; i++)
cin >> p[i];

ll prob[n + 1][n + 1];

// probability of one heads with one coins
prob = p;

// probability of no heads with one coins
prob = 1 - p;

for (int i = 2; i <= n; i++)
// probability of no heads with i coins.
prob[i] = prob[i - 1] * (1 - p[i - 1]);
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++)
// probability of head at ith coin it it occurs at(i-1)
// then just multiply with tail probability otherwise
prob[i][j] = prob[i - 1][j - 1] * p[i - 1] + prob[i - 1][j] * (1 - p[i - 1]);
}

ll sum = 0;

for (int i = n / 2 + n % 2; i <= n; i++)
// take those probability which have more heads than tails.
sum += prob[n][i];

cout << "The probability of heads more than the tails is: ";
cout << setprecision(10) << sum << "\n";
}

return 0;
}
```

Output

```Enter number of test cases: 3
Enter the number of coins: 5
Enter the probabilities of head: 0.42 0.01 0.42 0.99 0.42
The probability of heads more than the tails is: 0.3821815872
Enter the number of coins: 3
Enter the probabilities of head: 0.30 0.60 0.80
The probability of heads more than the tails is: 0.612
Enter the number of coins: 1
Enter the probabilities of head: 0.50
The probability of heads more than the tails is: 0.5
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates