Set 35 (2 Eggs and 100 Floors) | Puzzles for Interview - Interview Preparation PDF Download

Introduction

The 2 Eggs and 100 Floors puzzle involves finding out which floors in a 100-story building are safe to drop eggs from and which will cause the eggs to break on landing. The challenge is to minimize the total number of drops in the worst-case scenario and to find the required floor.

Assumptions

Before starting the puzzle, we need to make a few assumptions. We assume that an egg that survives a fall can be used again, and a broken egg must be discarded. The effect of a fall is the same for all eggs. If an egg breaks when dropped, it would also break if dropped from a higher floor. If an egg survives a fall, it would survive a shorter fall.

Method 1

If we have only one egg, the experiment can be carried out in only one way. We can drop the egg from the first-floor window and then continue upward until it breaks. This method may require up to 100 droppings in the worst-case scenario.

Method 2

Suppose we have two eggs available. What is the least number of egg droppings that are guaranteed to work in all cases? The problem is not to find the critical floor, but to decide on which floors to drop the eggs to minimize the total number of trials.

Binary Search Method

If we use the Binary Search Method and start from the 50th floor, we can end up doing 50 comparisons in the worst-case scenario. The worst-case happens when the required floor is the 49th floor.

Optimized Method

To optimize the solution, we can use the following equation: x(x-1)/2=100, where x is the number of trials. We start our first attempt on the 14th floor. If the egg breaks on the 14th floor, we try the remaining 13 floors one by one. If the egg does not break, we jump to the 27th floor. If the egg breaks on the 27th floor, we try the floors from 15 to 26. If the egg does not break on the 27th floor, we go to the 39th floor, and so on. The optimal number of trials in the worst-case scenario is 14.

Conclusion

The 2 Eggs and 100 Floors puzzle can be solved using different methods. The optimized method helps us minimize the total number of trials in the worst-case scenario. It is essential to make assumptions and choose the right strategy to solve the puzzle efficiently.