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
from math import log2 NEW_LINE MAX = 100001 NEW_LINE dp = [ 0 ] * MAX NEW_LINE def probability ( k , n ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( k , n + 1 ) : NEW_LINE INDENT res = dp [ n ] - dp [ i ] - dp [ n - i ] - n NEW_LINE ans = ans + pow ( 2.0 , res ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def precompute ( ) : NEW_LINE INDENT for i in range ( 2 , MAX ) : NEW_LINE INDENT dp [ i ] = log2 ( i ) + dp [ i - 1 ] NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT precompute ( ) NEW_LINE print ( probability ( 2 , 3 ) ) NEW_LINE print ( probability ( 3 , 6 ) ) NEW_LINE print ( probability ( 500 , 1000 ) ) NEW_LINE DEDENT