kbgrant

I was asked this question at a Google interview in 2006. At that time I worked it out mathematically as the author has here. Only afterwards did I realize that it is a simple Dynamic Programming problem.

Let f(y) be the number of drops required with y floors remaining. At a drop from floor x, either the egg breaks and you must test all floors from 1 to x-1, or else the egg does not break and you have reduced to a smaller sub-problem with y-x floors. So the number of drops required is 1 (for the current drop) plus the max of either x-1 or f(y-x). We simply minimize this value over all potential floors x from 1 to y.

Here is a solution in C++: https://gist.github.com/3156157