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
< ? php function binomialCoeff ( $ x , $ n , $ k ) { $ sum = 0 ; $ term = 1 ; for ( $ i = 1 ; $ i <= $ n && $ sum < $ k ; ++ $ i ) { $ term *= $ x - $ i + 1 ; $ term /= $ i ; $ sum += $ term ; } return $ sum ; } function minTrials ( $ n , $ k ) { $ low = 1 ; $ high = $ k ; while ( $ low < $ high ) { $ mid = ( $ low + $ high ) / 2 ; if ( binomialCoeff ( $ mid , $ n , $ k ) < $ k ) $ low = $ mid + 1 ; else $ high = $ mid ; } return ( int ) $ low ; } echo minTrials ( 2 , 10 ) ; ? >