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
< ? php $ MAX = 100001 ; $ dp = array_fill ( 0 , $ MAX , 0 ) ; function probability ( $ k , $ n ) { global $ MAX , $ dp ; $ ans = 0 ; for ( $ i = $ k ; $ i <= $ n ; ++ $ i ) { $ res = $ dp [ $ n ] - $ dp [ $ i ] - $ dp [ $ n - $ i ] - $ n ; $ ans += pow ( 2.0 , $ res ) ; } return $ ans ; } function precompute ( ) { global $ MAX , $ dp ; for ( $ i = 2 ; $ i < $ MAX ; ++ $ i ) precompute ( ) ; echo probability ( 2 , 3 ) . " STRNEWLINE " ; echo probability ( 3 , 6 ) . " STRNEWLINE " ; echo probability ( 500 , 1000 ) ; ? >