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
import java . math . * ; class GFG { static int MAX = 100001 ; static double dp [ ] = new double [ MAX ] ; static double probability ( int k , int n ) { double ans = 0.0 ; for ( int i = k ; i <= n ; ++ i ) { double res = dp [ n ] - dp [ i ] - dp [ n - i ] - n ; ans += Math . pow ( 2.0 , res ) ; } return ans ; } static void precompute ( ) { for ( int i = 2 ; i < MAX ; ++ i ) dp [ i ] = ( Math . log ( i ) / Math . log ( 2 ) ) + dp [ i - 1 ] ; } public static void main ( String args [ ] ) { precompute ( ) ; System . out . println ( probability ( 2 , 3 ) ) ; System . out . println ( probability ( 3 , 6 ) ) ; System . out . println ( probability ( 500 , 1000 ) ) ; } }