2 Eggs and 100 Floors Problem (Solved)

The 2 Eggs and 100 Floors problem is frequently asked in interview to evaluate candidate’s understanding on linear search and binary search. I have tried to explain this problem as easy as possible.

Problem Statement

There is a building of 100 floors. One of the floors is the highest floor (say Nth floor) an egg can be dropped from without breaking.

• If an egg is dropped from that floor (N) or above (N+1, N+2, …), it will break.
• If it is dropped from any floor below (N-1, N-2, …), it will not break and you can drop the egg again.

Given two eggs 🥚🥚, find the floor (N) an egg can be dropped from without breaking in minimum number of drops.

The question is, What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

Think about the problem for a few minutes, and then read on.

Solution 1 (Liner Search)

First solution is linear search strategy which is very straightforward if we don’t care about number of drops. We can start dropping egg from floor 1, floor 2, floor 3 and continue till floor 100 until we find the floor N. In worst case it will take 100 drops if egg breaks only at the last (100th) floor.

    Linear search - worst case - 100 drops

Can we improve worst case using binary search strategy? Lets see in Solution 2.

Solution 2 (Binary Search)

Second solution is binary search strategy where we start from the middle (50th) floor.

• If egg breaks on 50th floor that means our N is below 50.
• If egg doesn’t break that means our N is above 50.

Binary search strategy say that If egg breaks on 50th floor then we should check now from 25th floor but wait, we have a problem here. We have already lost 1 egg and left with only 1 egg now so we are left with linear search only but in this case only from 1st to 50th floor in worst case. So our drops came down to half compare to solution 1

    Binary Search - worst case - 50 drops

Can we still improve the worst case? Let see in Solution 3

Solution 3 (Divide and Conquer)

Let’s apply our learning from previous solutions and apply a mix of linear and binary approach.

This time we start off by dropping an egg at floor 10, floor 20, floor 30 …increasing floor by 10

• If first egg breaks at floor 10, then we use second egg to linear search from 1 to 9

• If first egg breaks at floor 20, then we use second egg to linear search from 11 to 19

• ….

• In worst case if egg breaks at last (100th) floor then we use second egg to linear search from 91 to 99. In worst case it will take 19 drops (10th, 20th, 30th …… 70th 80th 90th 91th ….99th)

    Divide and Conquer - worst case - 19 drops
  

Now when we came to an understanding, lets see Solution 4

Solution 4 (Equation)

What we need is a solution that minimizes our maximum drops. The solution above hint towards what we need is a strategy that tries to make solutions to all possible answers the same depth (same number of drops). The way to reduce the worst case is to attempt to make all cases take the same number of drops.

As I hope you can see by now, if the solution lays somewhere in a floor low down, then we have extra-headroom when we need to step by singles, but, as we get higher up the building, we’ve already used drop chances to get there, so there we have less drops left when we have to switch to going floor-by-floor.

Let’s break out some algebra.

Imagine we drop our first egg from floor n, if it breaks, we can step through the previous (n-1) floors one-by-one.

If it doesn’t break, rather than jumping up another n floors, instead we should step up just (n-1) floors (because we have one less drop available if we have to switch to one-by-one floors), so the next floor we should try is floor n + (n-1)

Similarly, if this drop does not break, we next need to jump up to floor n + (n-1) + (n-2), then floor n + (n-1) + (n-2) + (n-3) …

We keep reducing the step by one each time we jump up, until that step-up is just one floor, and get the following equation for a 100 floor building:

n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100

This summation, as many will recognize, is the formula for triangular numbers (which kind of makes sense, since we’re reducing the step by one each drop we make) and can be simplified to:

n (n+1) / 2 >= 100

This is a quadratic equation, with the positive root of 13.651 (Which we have to round up to 14)

This means we want to start dropping from floor 14, jump up 13 floors to drop from floor 27, jump up 12 floors to drop from floor 39, and so on. Our worst case scenario is then a drop count total of 14.

    Equation - worst case - 14 drops

Drop	Floor
#1	14
#2	27
#3	39
#4	60
#6	69
#7	77
#8	84
#9	90
#10	95
#11	99
#12	100