Fog Creek Software
Discussion Board

Eggs problem

There's a building with 100 levels and you have two eggs. You can drop an egg from any level of the building to check whether it breaks or not. After it broke it is useless.

It is known that below a certain level eggs do not break and from that level up they always break.

The question is that which level it is? Tell me the minimum number of drops that will ALWAYS identify that level!

Generalization: N levels and k eggs...


Levente Mészáros
Wednesday, December 08, 2004

int FindSafeLevel(void) {

  int a,

  for (level = 10; level <=100; level = level + 10) {

      if (EggDrop(level) == EGG_BREAK) {

        for (a = level - 9; a < level; a++) {

            if (EggDrop(a) == EGG_BREAK) {
              return a - 1;
        return level - 1;

  return 100;

So, at most 19 tests.  Minimum 10 tests.

Am I close?

Wednesday, December 08, 2004

Generalization would be...

Square root the total levels and that will be your starting level.  Min will be the square root of the levels +/- 1 for integer rounding to a Max of  2 * Min - 1 give or take a level.

Wednesday, December 08, 2004

I should clarify the minimum tests.  The minimum test for the local worst cases of the (multiples of 10) - 1.

Actually starting at level 9 and even 8 with a jump of 9 and 8 will yeild the same maximum tests as 10 but have a slightly larger average test count.

Wednesday, December 08, 2004

The solution is not so trivial.

Wednesday, December 08, 2004

Damn...  I guess I'm not hiring material.

Thursday, December 09, 2004

It's similar to a binary search. You can determine the floor in log2 (100) = 7.

Tuesday, December 21, 2004

*  Recent Topics

*  Fog Creek Home