The Egg Dropping Puzzle

Suppose a building has n floors. If we have m eggs, how can we find the minimum number of drops needed to determine from which floors it is safe to drop an egg (in other words, it won’t break)?

Just to clarify the problem, here are the rules:

• There exactly n floors and m eggs
• If an egg does not break from a given floor, it will also not break on any lower floor
• If an egg breaks when dropped from a given floor, it will also break on any higher floor
• If an egg breaks, it must be discarded

There are several ways to go about this problem. We’ll present a recursive and a bottom-up dynamic programming approach here.

Method 1: Recursion

Notice that this recursive method is very, very inefficient! Just try running this function for 36 floors and 2 eggs, and you’ll see what I mean. This is because the recursive calls recalculate the same sub-problems over and over again. This is where dynamic programming can help.

Method 2: Dynamic Programming

Ah, much better. Now if we run this function for 36 floors and 2 eggs, the program finishes executing almost instantly. The reason the dynamic programming approach is so much more efficient than the recursive approach is because here we are storing the result of each sub-problem in an array, called memo. Therefore, instead of having to re-evaluate each sub-problem, we calculate each sub-problem once and simply refer to the memo array if we need that result again.

Thanks for reading! If you find an error in this post, please feel free to comment below and I will do my best to address any issues.