Two Eggs Puzzle

Statement

You have two eggs, and access to a 100 story building. The eggs you have are specially strong eggs. There is some floor on the building below which the eggs will not break, if dropped. What is the most number of drops you need to perform in order to guarantee that you will find that floor? In other words, what is the worst upper case bound on the number of drops you must make to determine this floor?

Background

This puzzle has got quite an attention in recent past as a problem frequently posed in tech interviews with different tech giants such as Google, Amazon etc. Fun of the problem is that you can come up with a solution quite easily, but may be that solution, even though correct, won’t be the best one. So you would be iteratively asked if you could do better than that, and thus it makes it a very good interview question to determine your problem solving skills.

Naive Solution

You can start with the most naive solution of all. Start at 1st floor, and continue upwards trying each floor. Thus in worst case, you will need 100 drops to determine the floor below which the eggs will not break. This does guarantee that you will find your desired floor, but it is inefficient. You never make use of the second egg provided to you.

Improving By Increasing Steps For First Egg

So you can improve on the previous method. This time say, instead of starting at 1st, start at floor 2nd, and continue upwards with steps of two. So you try 2nd floor, then 4th, 6th, 8th, and so on. Whenever the first egg breaks, you try the second egg on the floor below the current one. So say the first egg broke at 50th floor, then you use the second egg to determine whether 49th floor is your desired floor or not. If second egg breaks when dropped from 49th floor, then 49th is your desired floor. Otherwise, floor 50th. How many drops do you need here in worst case? Worst case will be when you reach the 100th floor, and first egg breaks. Thus you will require 50 drops to get to 100th floor, and one more to determine the status of 99th floor. This makes it 50+1 = 51 drops.

While better then the naive solution. We can still do better. What happens if we start at 3rd floor, and continue in steps of 3. So we try 3rd, then 6th, then 9th, and so on. Whenever the first egg breaks, we have two more floors to test, with the second egg. Say the first egg broke on Xth floor, then we must check for floor X-1, and X-2 with the second egg. But how do we do that? How do we test two floors with one egg? Well, you have to perform a linear search on the second egg in this case. There is no other way to go with the second egg, but the naive solution we thought of initially for the first egg, i.e. linear search. So if first egg broke at  69th floor, we test floor 67 with the second egg, and if it doesn’t break, then 68th.

How many drops do we need in worst case when using a step of 3? Worst case here will be when we reach floor 99th, and the first egg breaks. Then we use the second egg to try 97th and 98th floor. Thus, this makes a total of 99/3 + 2  = 35 steps. Certainly better then going in steps of 2 floors.

We have established one fact. With the second egg, we can perform only linear search. Otherwise there is no way to guarantee that we will reach our desired floor. Now we focus on the optimum step for first egg. Going up in steps of 3, was certainly an improvement over going up in steps of 2. Does that mean that the more we increase the step for first egg, the better? Actually no. Because, the more we increase the step for first egg, we also increase the linear search that has to be performed by the second egg. So say we use a step of 50. That is, we first try floor 50th with the first egg, and then 100th. What is the worst case scenario here? It’ll happen when the egg breaks at the 100th floor. Now we have to test floors 51-99 with the second egg. And this amounts to a total of 2+49 = 51 drops. Which isn’t better then when we used step of 3.

So we have to find the perfect balance between step for first egg, and length of linear search we would be performing with the second egg.

Striking The Perfect Balance

Lets say our final solution is P. That is, P is the maximum drops we need to guarantee a solution. What will be the step for first egg, for us to make sure that we won’t surpass a total of P drops. For the first drop, we must drop the first egg from the Pth floor, because if it breaks there, we’ll have P-1 floors remaining to try with the second egg. Thus it will make a total of 1+(P-1) = P drops. But what happens if the first egg doesn’t break at first drop. What floor do we try next? Since we have already used one of our P drops, we are only left with P-1 drops to try. So for our second attempt, we must choose the (P-1)th floor above the Pth floor, because if the egg breaks there, we will have P-2 floors to test, and P-2 drops left. Lets explain this with an example.

Say we choose our P to be 16. So at first attempt, we try 16th floor. If the egg breaks, we try floors 1 to 15 with the second egg. This makes it a total of 16 drops. But what if the egg doesn’t break at 16th? Since we have already used one of our drops, so now we are left with 15 tries. Next floor to try would be 16+15 = 31. So that, if the egg breaks at 31st floor, we’ll have floors 17-30 to try, which makes 14 floors, and a total of 14 drops left to try. Here goes the full list:

Step 1: 1 – 15 (if egg breaks at 16th)

Step 2: 17 – 30 (if egg breaks at 31st)

Step 3: 32 – 44 (if egg breaks at 45th)

Step 4: 46 – 57 (if egg breaks at 58th)

Step 5: 59 – 69 (if egg breaks at 70th)

Step 6: 71 – 80 (if egg breaks at 81st)

Step 7: 82 – 90 (if egg breaks at 91st)

Step 8: 92 – 99 (if egg breaks at 100th)

Thus this guarantees a maximum of P = 16 drops, in order to find our desired floor. We are in search for the minimum P using which we can reach the 100th floor, i.e. minimum P which satisfies the following equation:

(1+(P-1)) + (1+ (P-2)) + (1 + (P-3)) + … + (1 + (P – P)) >= 100

Left hand side is an arithmetic series and equals: P(P+1)/2 >= 100

Solving for P, the minimum integer that satisfies the equation is 14. And that is our answer. Thus we need a maximum of 14 drops, to ensure that we will reach our desired floor in worst case.

If you liked this post, subscribe to my feed.

Be Sociable, Share!

5 thoughts on “Two Eggs Puzzle

  1. Hi Shuaib, Thanks for the puzzle. It was a nice one and I had fun solving it. However, I am getting a different answer to the problem.

    I am getting 18 as the max no. of drops and not 14. I approached the problem from a partitioning point of view. I can show you how I solved it but wanted to check with you first. With P=14, what floor would you start dropping the eggs? With 18 as the max. no of drops, I start at the 10th floor. A partition size of 10 is where I get a local minima. If we go either way the max. # of drops increases.

    Also, I have assumed here that if I am at the 99th floor and still the eggs don’t break, then the eggs must break when dropped from the 100th floor ( i.e. the eggs *must* break when dropped from one floor or the other) and I don’t need to verify by dropping it from the 100th floor.

    So, the worst case ( or max # of drops) is when we are closest to the 100th floor. I can explain the equation I derived in my next post, but when I tried to verify empirically all combination starting from 5th to 20th floor, and then going higher in multiples of that number ( i.e. in case of 5, start at 5th floor then move up in multiples of 5 floor or start at floor # 20 and then move up in multiples of 20, when solution is not found) I couldn’t get any floor where I can start and arrive at P=14. Do you know which floor to start from to get the solution of 14?

    Thanks

  2. Hi Shuaib, never mind. I might have written too soon. I jumped at the solution without trying to understand the solution. Sorry about that. I think I get it now. Thanks. That was pretty good.

Leave a Reply