003.Two Eggs Problem

•  You are given 2 eggs.
•  You have access to a 100-storey building.
•  Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
•  You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
•  Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Answer: Maximum 14 drops

As a programmer your first thought may be to do something along the lines of a binary search. Go to the 50th floor drop an egg and if it breaks go to the 25th floor. Oops ... if it breaks on the 25th floor you will never find the answer. Not good!

Maybe start it the 50th floor an if it breaks start back at the 2nd floor and drop until the second egg breaks. That would work and at worst you would have made 49 drops ... first at the 50th then 2-49. Okay but not optimal.

What if it doesn't break on the 50th floor? Go to the 100th floor? You would still have a worst case the same as if it had broken on the 50th floor.

So what if you start out on say the 20th floor? If the egg doesn't break then go up to the 39th floor, etc. This way you are narrowing in without increasing your worst case.

It turns out that the most optimal floor to start on is the 14th then move up to the n+(n-1) floor (14+(14-1)=27), etc. Worst case the first egg breaks on the 14th floor and you have to go back to the 2nd floor and the second egg breaks on the 13th floor. In this case you have made 13 drops. If the egg doesn't break until you have gone all the way to the 100th floor then you have only made 12 drops. The attempts would be on floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100. Not to mention you still have at least one egg for breakfast :).

I'll leave it up to you math wizards out there to come up with the formula for 2 eggs and a building of N floors