Open Close Principle
August 29, 2012
Difference between struct and class in C++
September 3, 2012

Dropping egg puzzle

You have two identical eggs and access to a 100 floor building.
You don’t know how strong the eggs are. Eggs can be really strong (may not break if dropped from 100th floor) or fragile (break if dropped from first floor).
You want to find out the highest floor from where an egg can be dropped without breaking. In the process you may break both the eggs.
Question is, At least How many drops you need to find the highest floor?

Linear Solution:

Start from the first floor, and keep moving one floor up at a time. From each floor drop the egg and see if it breaks.

If the egg breaks at the k’th floor, then Answer is k-1.

Note that this is the only way to solve the puzzle if we have only one egg.

Number of Drops required in the worst case: 100.

Absolute Binary Solution:

In this solution we divide the interval (100 floors) in 2 equal halves.

Drop the egg from 50'th floor
    - If Egg breaks
       Try with the 2'nd egg starting from 1'st floor till 50'th in a linear way.
    - If Egg does not break.
        Drop the egg from the 75'th floor.
And so on.

 Number of drops required in the worst case: 51

Fixed Interval Approach:

Take an example for Interval = 2.

int k=2
WHILE (k <=100)
    Drop egg from k'th floor
    IF it breaks
        Drop Egg from (k-1)'th floor
        IF it breaks Answer is (k-2)
        ELSE Answer is (k-1)
    ELSE
        k = k+2

Number of drops required for Interval = 2:  51

The Idea is same increment k by the Interval Size. If egg breaks, then try with the second egg in a linear way from last interval+1.

Let us see how Number of drops wary with the intervals.

Interval          Number of Drops Required
---------         ------------------------
   1                  100
   2                  51
   3                  35
   4                  28
   5                  24
   6                  21
   7                  20
   8                  19
   9                  19
   10                 19
   11                 19
   12                 19
   13                 19
   14                 20
   15                 20
   16                 21

Minimum No of drops required is: 19 (For Interval 8, 9 , 10, 11, 12 and 13)

Variable Interval Approach:

In this case we will not consider the same interval every time.

Let x be the number of drops required to find the correct floor number.

So after the first egg is broken we can have x-1 drops. So one way to attain this number of drops=x is
 – Drop the egg from height x.

If the egg does not break in the First Drop (from height x). Then we are left with (x-1) drops to go. Out of these (x-1) drops 1 will be used by the first egg (not yet broken) and rest (x-2) by the 2nd egg (if the first one is broken).
 – Drop the egg from height (x-1). (actually floor no: x+(x-1) )

And so on.

We just need to find the value of x.

Let’s take an example:

Let x = 19 ( i.e 19 drops required to find the floor number). This is the answer which we have got in the last section.

First we drop from height 19.
  - If it breaks, try 2'nd egg from floor 1 to 18
Else, we are left with 18 drops (Not 18 floors but 18 DROPS)
   Drop from a height 19+18 = 37
     - If it breaks, try 2'nd egg from floor 20 to 36.
Else, we are left with 17 drops
   Drop from a height 37+17 = 54
     - If it breaks, try 2'nd egg from floor 38 to 53
Else, We are left with 16 drops
   Drop from a height 54+16 = 70
     - If it breaks, try 2'nd egg from floor 55 to 69
Else, We are left with 15 drops
   Drop from a height 70+15 = 85
     - If it breaks, try 2'nd egg from floor 71 to 84
Else, We are left with 14 drops
   Drop from a height 85+14 = 99
     - If it breaks, try 2'nd egg from floor 86 to 98
Else, We are left with 13 drops
And we can find the answer in just one drop (from floor 100).

Hence 19 is not the Optimal Answer, and we can find a smaller value for x.

From the above solution, it is clear that the optimal solution will require 0 linear trials in the last step.

Hence, the corresponding mathematical equation will be:

X + (X-1) + (X-2) + … + (1) >= 100

Solving the equation for 100, we get

X = 14.

Minimum Number of Drops will be: 14.

i.e drop the first egg from following floors until it breaks: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100…
If at any point it breaks, start the 2’nd egg linearly from (previous floor + 1).

 

Leave a Reply

Your email address will not be published. Required fields are marked *