Q:

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

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```

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```