# 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
The probability of having (Coin1,Coin2,Coin3) = (Head,Head,Head)
is 0.3×0.6×0.8 = 0.144;
The probability of having (Coin1,Coin2,Coin3) = (Tail,Head,Head)
is 0.7×0.6×0.8 = 0.336;
The probability of having (Coin1,Coin2,Coin3) = (Head,Tail,Head)
is 0.3×0.4×0.8 = 0.096;
The probability of having (Coin1,Coin2,Coin3) = (Head,Head,Tail)
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 ProgrammingSince the problem can be solved with recursion with time complexity of

which is not accepted as there are other better approach to solve the problem with time complexity ofO(2^n);O(n*n)Let's assume

to be the probability of gettingprob[i][j]heads with firstjcoins. To getiheads at thejposition, there are two possibilities:ithIf the number of heads till

coins is equal to(i - 1)then a tail comes atj. If the number of heads tillithcoins is equal to(i - 1)then a head comes at(j - 1)position.ithThe probability of occurring jth head at ith coin toss depends on the number of heads in

coins, if(i-1)thcoin have(i-1)head then(j-1)coin occurs atjthcoin(ith), and ifp[i]coins have already(i-1)coins then atjtoss tails come(jth).1-p[i]Pseudo Code:Time complexity: In worst caseO(n*n)C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput