Classic 2 Egg Problem

Problem Statement

You are given 2 identical eggs. You are standing before 100 storey building. Eggs are so hard that they can be broken only above certain floor. You have to find the floor above which eggs break (Highest floor from which egg can be dropped without breaking) in minimal number of attempts.

Easy Approach

Binary Divide - Reduce Problem Space by 2

Easy way to think the solution is "Binary Division". Let's divide the problem space of 100 floors into two 50 floor problem spaces. Start dropping the first egg at the middle floor (50th floor). In case egg is broken you know that highest floor from which egg can be dropped without breaking it is one of bottom 50 floors (1st-50th floor) and if egg is not broken then higest floor from which egg can be dropped without breaking it is among the top 51 floors (50th-100th floor). This way we have reduced problem space to 50 after first attempt.

Lets take both cases. In first case when egg is broken you have left with one egg and no choice other than trying dropping the egg from each floor starting from first floor and going upward by one floor each time. This case you have to drop the egg max upto 50 times to find the solution (In this case egg can be broken only if it is dropped from 50th floor or above). In second case let's apply "Binary Division" approach again and drop the egg at 75th floor. If egg is broken the solution is between 51-75 otherwise 76-100. In both case number of attempts will be less than 50 so let's discard them.

Refined Approach

Trinary Divide - Reduce Problem Space by 3

Let's think some better way to reduce the number of attempts. Instead of "Binary Divide", let's use "Trinary Divide". Drop the egg from 33rd floor (100/3). If egg is broken then we have to start from first floor just like we did in "Binary Divide". In this case we have to try max upto 33 times (Worst case : Egg is broken from 33rd floor onward). In case of egg is not broken from 33rd floor then we are left with 67 floors (34th floor - 100th floor). In second attempt we will drop the egg from 66th floor which will divide our problem space from 67 floors to 33/34 floors based on egg is not broken or broken. After two attempts we have divided the problem space by 3. In this case maximum attempts are 2+33 = 35.

Let's improve over above approach and divide the problem space(100 floors) in four parts. In this case first egg will be dropped from 25th floor. In this case max attempts are 3+24 = 27 (When egg is broken from 75th floor onward).

We can keep refining approach by reducing the problem space further. If we divide the problem space in 10 parts then max attempts are 9+9 = 18 (when egg is broken from 90th floor onward)
These attempts and results are

1.Drop @ Floor 10 - Egg is not broken
2.Drop @ Floor 20 - Egg is not broken
3.Drop @ Floor 30 - Egg is not broken
4.Drop @ Floor 40 - Egg is not broken
5.Drop @ Floor 50 - Egg is not broken
6.Drop @ Floor 60 - Egg is not broken
7.Drop @ Floor 70 - Egg is not broken
8.Drop @ Floor 80 - Egg is not broken
9.Drop @ Floor 90 - Egg is broken
10.Drop @ Floor 81 - Egg is not broken
11.Drop @ Floor 82 - Egg is not broken
12.Drop @ Floor 83 - Egg is not broken
13.Drop @ Floor 84 - Egg is not broken
14.Drop @ Floor 85 - Egg is not broken
15.Drop @ Floor 86 - Egg is not broken
16.Drop @ Floor 87 - Egg is not broken
17.Drop @ Floor 88 - Egg is not broken
18.Drop @ Floor 89 - Egg is not broken

After 18 attempts we found that egg can be broken 90th floor onward.

Best Approach

Irregular Divide - Reduce Problem space with each attempt

In above approach we were dividing the problem space in equal parts. Problem space was not reducing with each attempts. Let's try to reduce the problem space with each attempt. Let's assume we have max n attempts. So if we drop our egg at nth floor and it is broken we have left with n floors so we can find the solution in n attempts. In case egg is not broken solution is in (100-n) floor. With second attempts we should reduce the problem space by 1 so let's drop the egg from n+(n-1) floor. In case egg is broken our problem space is reduced to n-1 floor (From n+1 To 2n-1). In this case we have to try max n times to find solution. If egg is not broken in third attempt we should drop egg from n+(n-1)+(n-2) floor so that problem space can be reduced to n-2 in case egg is broken.

We have to repeat this exercise till problem space is reduced to 1 floor and sum of all this must be 100. It means n+n-1+n-2+n-3....+3+2+1 >= 100 => Min value of n = 14

So One of Worst Case is


1.Drop @ Floor 14 - Egg is not broken
2.Drop @ Floor 27 - Egg is not broken
3.Drop @ Floor 39 - Egg is not broken
4.Drop @ Floor 50 - Egg is not broken
5.Drop @ Floor 60 - Egg is not broken
6.Drop @ Floor 69 - Egg is not broken
7.Drop @ Floor 77 - Egg is not broken
8.Drop @ Floor 84 - Egg is not broken
9.Drop @ Floor 90 - Egg is not broken
10.Drop @ Floor 95 - Egg is not broken
11.Drop @ Floor 99 - Egg is broken
12.Drop @ Floor 96 - Egg is not broken
13.Drop @ Floor 97 - Egg is not broken
14.Drop @ Floor 98 - Egg is not broken

Solution
14 Attempts