Egg Dropping Problem

Idea.md

K - Number of eggs - given N - Number of floors - given A - Minimum number of attempts - to find

Egg dropping puzzle follows binomial expansion.

1 egg - N floors - A attempts

N = A/1!

2 eggs - N floors - A attempts

N = A/1! + A(A-1)/2!

3 eggs - N floors - A attempts

N = A/1! + A(A-1)/2! + A(A-1)(A-2)/3!

K eggs - N floors - A attempts

N = A/1! + A(A-1)/2! + ... + A(A-1)(A-2)...(A-K-1)/K!

Now for K eggs, N floors, A attempts, we have to stop computing when it exceeds N - O(K)

Linear Search

Starting from A as 1, we can run the computation and see if it reaches N then for A as 2 ... Finally we will get A which exceeds N - O(N)

Binary Search

Since this finding A is an increasing sequence, we can go for binary search. We have to find A which is immediately greater than N - O(log N)

Hence total running time: O(K log N)

Here is the implementation: Code Reference: Reference

What is the answer when #floor =2 and #egg=1?