Suppose you have two eggs and you want to determine from which floors in a one-hundred floor building you can drop an egg such that it doesn’t break. You are to determine the minimum number of attempts you need in order find the critical floor in the worst case while using the best strategy.
- If the egg doesn’t break at a certain floor, it will not break at any floor below.
- If the eggs breaks at a certain floor, it will break at any floor above.
- The egg may break at the first floor.
- The egg may not break at the last floor.
If the eggs were unlimited, my best strategy would be using Binary Search. That is, we search from the 50th floor. If the egg breaks, we drop it again on the 75th floor. If the egg doesn’t break, we drop it on the 25th floor. Each time, we reduce the difference of the floors by half. By using this strategy, we would only use at most eggs and thus attempts.
So, what makes this problem interesting? We have only 2 eggs! Now, I am going to reveal the first attempt of the best strategy, spoilers ahead!
Drop the egg on the 14th floor.
What’s so special about the 14th floor? If the egg doesn’t break on the that floor, that means the critical floor must be below 14. The second step of our strategy would be ：
Drop the egg from the 1st to 13th floor.
Following this strategy, our maximum attempts would be 14 (when the eggs broke on all 13 floors). Now, what if the egg doesn’t break on the 14th floor? The strategy is :
Drop the egg on the 27th floor.
If the egg breaks, we need to search only from 15th floor to the 23rd floor, in total of 14 attempts, same as the worst case for when the egg broke on the 14th floor. Have you noticed the pattern yet? If the egg breaks on the 100th floor, we would drop the egg in a sequence of floor .
2 eggs, N floors
Now, we generalize the problem into floors. Supposed that the maximum attempts for the best strategy is . Then, we should drop the egg on the floor, so that if the egg breaks we can apply linear search from the 1st floor to the th floor. If the egg doesn’t break, we would drop it on floor , and so on until we reached the highest floor. Recognize this pattern? Yes, it’s an arithmetic sequence summation. The formula is
We might not reach exactly on the th floor, so we need a summation at least greater than .
The solution for is trivial. However, the discussion on this problem has not end yet. In the next post, we shall discuss the case for eggs, floor and implement the algorithms for it. Stay tuned!