Question: Figure out the highest floor of a 100-floor building an egg can be dropped without breaking, given two eggs. You are to determine the minimum number of attempts required in the worst case scenario to find the critical floor.
Answer: Following are the logical assumptions that can be made-
- If the egg doesn’t break at a certain floor, it will not break at any floor below.
- If the eggs break at a certain floor, it will break at any floor above.
We can find the minimum number of attempts to find the critical floor using binary search. We would have to drop the first egg from the 50th floor. If it doesn’t break, we would drop the same egg from the 75th and so on; in the best case scenario we would be able to cover all floors with 7 drops.
But if the first egg broke in the first attempt, i.e. 50th floor, we would have only one egg remaining to find the critical floor. Therefore, this would take us 49 more tests. However, we can do better if we drop the egg at a lower floor, as we will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg.
If we drop the first egg from nth floors, we would need 1 + (n – 1) attempts, if the egg breaks. If the egg doesn’t break, we drop it from (n + n)th floor. If it breaks now, we would need 1 + (1 + (n-1)) total attempts. Since there are 100 floors we would need [100 / n] attempts from first egg, and n – 1 attempts from second egg in the worst case. Following this strategy, we see that n = 8 (also 9, 10, 11, 12, 13) gives the optimal answer (minimising [100 / n] + n – 1), with total attempts equalling 10 + 9 = 19.
With n = 13 (or any other answer), optimal solution is lot higher than (1 + (1 – n)) = 14, which is number attempts if first egg breaks in first attempt. In other words, if first egg breaks at first attempt, it won’t be our worst case. Maybe we can find a better strategy.
In order to optimize things, we can say that if egg breaks in first attempt, total number of attempts should be very close to optimal solution. Infact we should try to make all possible scenarios take the same number of drops.
Or number of attempts by egg1 + number of attempts by egg2 should be almost same for all possible scenarios. This can be achieved if we reduce number of attempts by egg2 by 1 every time we drop egg1.
Therefore, if we drop first egg from nth floor, next we would be dropping if from (n + (n – 1))th floor. So we would drop first egg from these floors (if it doesn’t break)-
n, n + (n-1), n + (n-1) + (n-2), …, n + (n-1) + (n-2)+ … + 2 + 1
Since we have 100 floors, n + (n-1) + (n-2) + … + 2 + 1 should be 100.
Solving this equation, we get n = 13.651, which rounds up to 14. Hence the first egg needs to be dropped from these floors (if not broken)-
In the figure below, we compare both the startegies