Probability of getting at least K heads in N tosses of Coins | Dynamic and Logarithm approach find probability of at least k heads ; dp [ i ] is going to store Log ( i ! ) in base 2 ; Initialize result ; Iterate from k heads to n heads ; Preprocess all the logarithm value on base 2 ; Driver code ; Probability of getting 2 head out of 3 coins ; Probability of getting 3 head out of 6 coins ; Probability of getting 500 head out of 10000 coins
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100001 NEW_LINE double dp [ MAX ] ; double probability ( int k , int n ) { double ans = 0 ; for ( int i = k ; i <= n ; ++ i ) { double res = dp [ n ] - dp [ i ] - dp [ n - i ] - n ; ans += pow ( 2.0 , res ) ; } return ans ; } void precompute ( ) { for ( int i = 2 ; i < MAX ; ++ i ) dp [ i ] = log2 ( i ) + dp [ i - 1 ] ; } int main ( ) { precompute ( ) ; cout << probability ( 2 , 3 ) << " STRNEWLINE " ; cout << probability ( 3 , 6 ) << " STRNEWLINE " ; cout << probability ( 500 , 1000 ) ; return 0 ; }