How to solve the Two Egg Problem with N floors

Scenario

We have two identical eggs and access to a 100-story building. We must find the highest floor from which an egg can be dropped without breaking. We are also given the following constraints:

1. We can drop the eggs from any floor and see if they break or not.

2. If an egg breaks when dropped from a certain floor, it cannot be used again.

3. We want to minimize the number of egg drops required to find the highest safe floor.

Naive approach

The naive approach to solving the Two Egg Problem is a straightforward but inefficient strategy. In this approach, we start from the lowest floor and work our way up, dropping one egg at a time. Here are the steps of the naive approach:

1. Drop the first egg from the ground floor.

2. If the egg doesn’t break, move up one floor and drop it again.

3. Continue this process, going upward one floor at a time, until the first egg breaks.

The main drawback of this approach is that it requires many egg drops. If there are$N$floors in a building, we need to try$N$floors in the worst case.

Intermediate approach

Instead of trying every floor, we can divide the floors in intervals. A good heuristic is to divide the floors in such a way that the number of floors in each interval is equal to the number of intervals. This can be achieved using the square root function, which will divide$N$floors into roughly$\sqrt{N}$ intervals, each having roughly$\sqrt{N}$floors.

For a 100-storey building, the algorithm will proceed as follows:

1. Drop the first egg from the ground floor.

2. If the egg doesn’t break, move up$10$floors, and drop it again.

3. Continue this process, going$10$floors at a time, until the first egg breaks.

4. Once the first egg breaks, switch to the second egg. Start from the floor that we tested before and test one floor at a time.

5. Repeat this process until we find the highest floor at which the second egg doesn’t break.

Therefore, for a 100-storey building, we need to try$19$floors in the worst case.

Optimized approach

The optimized approach also divides the floors in intervals, but in a more intelligent way. Whenever we try dropping the first egg from a specific floor and it breaks, we switch to the previously tried floor and try going upward one floor at a time.

Now, let's suppose we drop the first egg from the$m^{th}$floor.

• If it breaks, we try the second egg from the previous$m-1$floors, one at a time.

• If it doesn’t break, instead of jumping$m$floors, we jump$m-1$floors, because we’re left with one less drop as we’ve already tried dropping the first egg from the$m^{th}$floor. Therefore, the next floor we should try is$\bigl( m+(m-1) \bigr)^{th}$floor.

Therefore, we keep reducing one floor in every next jump until we’re left with a jump of only one floor.

Using the arithmetic series sum formula, the inequality above can be simplified as:

Let’s solve this equation for a 100-storey building:

The inequality above is quadratic which yields a positive root of $13.65$, which we round up to $14$. Therefore, in case of a 100-storey building, the maximum number of tries required to find the highest floor from which an egg can be dropped without breaking is $14$.

Let’s try this solution for different number of floors using the code below:

In the code above:

• Line 4: We define the number of floors.

• Line 6: Then, we use the simplified quadratic formula to solve the equation and get the maximum number of floors.