Probability of getting more heads than tails when N biased coins are tossed | C ++ implementation of the above approach ; Function to return the probability when number of heads is greater than the number of tails ; Declaring the DP table ; Base case ; Iterating for every coin ; j represents the numbers of heads ; If number of heads is equal to zero there there is only one possibility ; 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 ; Driver Code ; 1 based indexing ; Number of coins ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; double Probability ( double p [ ] , int n ) { double dp [ n + 1 ] [ n + 1 ] ; memset ( dp , 0.0 , sizeof ( dp ) ) ; dp [ 0 ] [ 0 ] = 1.0 ; for ( int i = 1 ; i <= n ; i += 1 ) { for ( int j = 0 ; j <= i ; j += 1 ) { 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 ; for ( int i = ( n + 1 ) / 2 ; i <= n ; i += 1 ) ans += dp [ n ] [ i ] ; return ans ; } int main ( ) { double p [ ] = { 0.0 , 0.3 , 0.4 , 0.7 } ; int n = sizeof ( p ) / sizeof ( p [ 0 ] ) - 1 ; cout << Probability ( p , n ) ; return 0 ; }