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?
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.
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.