Given an array p[] of odd length N where p[i] denotes the probability of getting a head on the ith coin. As the coins are biased, the probability of getting a head is not always equal to 0.5. The task is to find the probability of getting heads more number of times than tails.
Examples:
Input: p[] = {0.3, 0.4, 0.7}
Output: 0.442
Probability for a tail = (1 – Probability for a head)
For heads greater than tails, there are 4 possibilities:
P({head, head, tail}) = 0.3 x 0.4 x (1 – 0.7) = 0.036
P({tail, head, head}) = (1 – 0.3) x 0.4 x 0.7 = 0.196
P({head, tail, head}) = 0.3 x (1 – 0.4) x 0.7= 0.126
P({head, head, head}) = 0.3 x 0.4 x 0.7 = 0.084
Adding the above probabilities
0.036 + 0.196 + 0.126 + 0.084 = 0.442Input: p[] = {0.3, 0.5, 0.2, 0.6, 0.9}
Output: 0.495
Naive approach: The naive approach would be creating all the 2n possibilities of heads and tails. Then calculating the probabilities for different permutations and adding them when the number of heads are greater than the number of tails just like the example explanation. This would give TLE when n is large.
Efficient approach: The idea is to use dynamic programming. Let’s assume dp[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 number of heads till (i – 1) coins is equal to j then a tail comes at ith.
- If number of heads till (i – 1) coins is equal to (j – 1) then a head comes at ith position
Hence, it can be broken into its subproblems as follows:
dp[i][j] = dp[i – 1][j] * (1 – p[i]) + dp[i – 1][j – 1] * p[i]
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to return the probability when// number of heads is greater than the number of tailsdouble Probability(double p[], int n){ // Declaring the DP table double dp[n + 1][n + 1]; memset(dp, 0.0, sizeof(dp)); // Base case dp[0][0] = 1.0; // Iterating for every coin for (int i = 1; i <= n; i += 1) { // j represents the numbers of heads for (int j = 0; j <= i; j += 1) { // If number of heads is equal to zero // there is only one possibility if (j == 0) dp[i][j] = dp[i - 1][j] * (1.0 - p[i]); else dp[i][j] = dp[i - 1][j] * (1.0 - p[i]) + dp[i - 1][j - 1] * p[i]; } } double ans = 0.0; // When the number of heads is greater than (n+1)/2 // it means that heads are greater than tails as // no of tails + no of heads is equal to n for // any permutation of heads and tails for (int i = (n + 1) / 2; i <= n; i += 1) ans += dp[n][i]; return ans;}// Driver Codeint main(){ // 1 based indexing double p[] = { 0.0, 0.3, 0.4, 0.7 }; // Number of coins int n = sizeof(p) / sizeof(p[0]) - 1; // Function call cout << Probability(p, n); return 0;} |
Java
// Java implementation of the above approachimport java.io.*;class GFG {// Function to return the probability when// number of heads is greater than the number of tailsstatic double Probability(double p[], int n){ // Declaring the DP table double [][]dp = new double[n + 1][n + 1]; // Base case dp[0][0] = 1.0; // Iterating for every coin for (int i = 1; i <= n; i += 1) { // j represents the numbers of heads for (int j = 0; j <= i; j += 1) { // If number of heads is equal to zero // there is only one possibility if (j == 0) dp[i][j] = dp[i - 1][j] * (1.0 - p[i]); else dp[i][j] = dp[i - 1][j] * (1.0 - p[i]) + dp[i - 1][j - 1] * p[i]; } } double ans = 0.0; // When the number of heads is greater than (n+1)/2 // it means that heads are greater than tails as // no of tails + no of heads is equal to n for // any permutation of heads and tails for (int i = (n + 1) / 2; i <= n; i += 1) ans += dp[n][i]; return ans;}// Driver Codepublic static void main(String[] args) { // 1 based indexing double p[] = { 0.0, 0.3, 0.4, 0.7 }; // Number of coins int n = p.length - 1; // Function call System.out.println(Probability(p, n));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the above approach import numpy as np# Function to return the probability when # number of heads is greater than# the number of tails def Probability(p, n) : # Declaring the DP table dp = np.zeros((n + 1, n + 1)); for i in range(n + 1) : for j in range(n + 1) : dp[i][j] = 0.0 # Base case dp[0][0] = 1.0; # Iterating for every coin for i in range(1, n + 1) : # j represents the numbers of heads for j in range(i + 1) : # If number of heads is equal to zero # there is only one possibility if (j == 0) : dp[i][j] = dp[i - 1][j] * (1.0 - p[i]); else : dp[i][j] = (dp[i - 1][j] * (1.0 - p[i]) + dp[i - 1][j - 1] * p[i]); ans = 0.0; # When the number of heads is greater than (n+1)/2 # it means that heads are greater than tails as # no of tails + no of heads is equal to n for # any permutation of heads and tails for i in range((n + 1)// 2, n + 1) : ans += dp[n][i]; return ans; # Driver Code if __name__ == "__main__" : # 1 based indexing p = [ 0.0, 0.3, 0.4, 0.7 ]; # Number of coins n = len(p) - 1; # Function call print(Probability(p, n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approachusing System;class GFG{ // Function to return the probability when// number of heads is greater than the number of tailsstatic double Probability(double []p, int n){ // Declaring the DP table double [,]dp = new double[n + 1, n + 1]; // Base case dp[0, 0] = 1.0; // Iterating for every coin for (int i = 1; i <= n; i += 1) { // j represents the numbers of heads for (int j = 0; j <= i; j += 1) { // If number of heads is equal to zero // there is only one possibility if (j == 0) dp[i,j] = dp[i - 1,j] * (1.0 - p[i]); else dp[i,j] = dp[i - 1,j] * (1.0 - p[i]) + dp[i - 1,j - 1] * p[i]; } } double ans = 0.0; // When the number of heads is greater than (n+1)/2 // it means that heads are greater than tails as // no of tails + no of heads is equal to n for // any permutation of heads and tails for (int i = (n + 1) / 2; i <= n; i += 1) ans += dp[n,i]; return ans;}// Driver Codestatic public void Main (){ // 1 based indexing double []p = { 0.0, 0.3, 0.4, 0.7 }; // Number of coins int n = p.Length - 1; // Function call Console.Write(Probability(p, n));}}// This code is contributed by ajit. |
Javascript
<script>// Javascript implementation of the above approach// Function to return the probability when// number of heads is greater than the number of tailsfunction Probability(p , n){ // Declaring the DP table var dp = Array(n + 1).fill(0).map( x => Array(n + 1).fill(0)); // Base case dp[0][0] = 1.0; // Iterating for every coin for(var i = 1; i <= n; i += 1) { // j represents the numbers of heads for(var j = 0; j <= i; j += 1) { // If number of heads is equal to zero // there is only one possibility if (j == 0) dp[i][j] = dp[i - 1][j] * (1.0 - p[i]); else dp[i][j] = dp[i - 1][j] * (1.0 - p[i]) + dp[i - 1][j - 1] * p[i]; } } var ans = 0.0; // When the number of heads is greater than (n+1)/2 // it means that heads are greater than tails as // no of tails + no of heads is equal to n for // any permutation of heads and tails for(var i = parseInt((n + 1) / 2); i <= n; i += 1) ans += dp[n][i]; return ans;}// Driver Code// 1 based indexingvar p = [ 0.0, 0.3, 0.4, 0.7 ];// Number of coinsvar n = p.length - 1;// Function calldocument.write(Probability(p, n));// This code is contributed by Amit Katiyar</script> |
0.442
Time complexity: O(n2), where n is the size of the given array.
Auxiliary space: O(n2) because using extra space for array dp
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
