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 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:
Time complexity: In worst case O(n*n)
C++ Implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer