Eggs dropping puzzle ( Binomial Coefficient and Binary Search Solution ) | Find sum of binomial coefficients xCi ( where i varies from 1 to n ) . If the sum becomes more than K ; Do binary search to find minimum number of trials in worst case . ; Initialize low and high as 1 st and last floors ; Do binary search , for every mid , find sum of binomial coefficients and check if the sum is greater than k or not . ; Driver Code
def binomialCoeff ( x , n , k ) : NEW_LINE INDENT sum = 0 ; NEW_LINE term = 1 ; NEW_LINE i = 1 ; NEW_LINE while ( i <= n and sum < k ) : NEW_LINE INDENT term *= x - i + 1 ; NEW_LINE term /= i ; NEW_LINE sum += term ; NEW_LINE i += 1 ; NEW_LINE DEDENT return sum ; NEW_LINE DEDENT def minTrials ( n , k ) : NEW_LINE INDENT low = 1 ; NEW_LINE high = k ; NEW_LINE while ( low < high ) : NEW_LINE INDENT mid = int ( ( low + high ) / 2 ) ; NEW_LINE if ( binomialCoeff ( mid , n , k ) < k ) : NEW_LINE INDENT low = mid + 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT high = mid ; NEW_LINE DEDENT DEDENT return int ( low ) ; NEW_LINE DEDENT print ( minTrials ( 2 , 10 ) ) ; NEW_LINE