Given
2 eggs and 100 floors such that eggs always break if dropped from
floors above a particular floor, find that particular floor in
minimum number of egg droppings.

If we had only 1 egg, then it would need to be dropped 100 times.

But with 2 eggs, some optimization can be done.

Example: Let's say we drop one egg from floor 50.

If it breaks, we are left with 1 egg and 50 floors and we have to try 50 times.

If it does not break, we can drop the same egg from floor 75 and recurse on same logic.

Note
that the starting floor ‘k’ (from where we begin
recursion) should have worst case order of ‘k’ if the egg
breaks and some other order ‘g’ (determined by higher
floors’ dropping strategy) if the egg does not break.

Minimum
droppings would be obtained when ‘k’ and ‘g’
would be equal else it would be greater of ‘k’ and ‘g’

If
we begin dropping from floor ‘k’ and egg breaks, then max
droppings needed = 1 + (k-1) = k

If
egg does not break, then max droppings for 100-k floors should also
be k if we want minimum no of droppings.

Suppose
after floor ‘k’, we choose floor ‘x’ to test
first egg again.

If egg breaks here, then max droppings needed = 1 + (x-k)

This quantity should also be equal to k

k = 1 + x-k

=> x = 2k-1 i.e. k-1 floors above floor k

This implies, that for minimum droppings, egg should be dropped after ‘k’
floors, then ‘k-1’ floors, then ‘k-2’ floors
and so on.

The sum of this series should equal 100 and last entry in this series
should be 1

=> k + (k-1) + (k-2) ... + 1 = 100

=> k(k+1)/2 = 100

=> k^{2} + k - 200 = 0;

Solving the above, k = (-1 + (1 - 4x(-200))^{0.5})/2

= (801^{0.5} - 1)/2

= 200^{0.5} - 0.5

= 14.1 - 0.5

= 13.6 which is 14 floors rounded off

Hence, we should begin from floor 14, then move to 14+13=27, then 27+12=39
and so on.

Max no of droppings required = 14

For 3 eggs, the starting floor can be increased beyond 14 because we know
that even if the egg breaks on this floor, we still have two eggs for the remaining below floors.

Increasing the starting floor is helpful even if the egg does not break on this starting floor, because
then the number of remaining floors above will be lesser.

Programatically, every floor presents us with 2 choices: egg breaks and egg does not break.

If egg breaks, then we are left with 1 less egg and k-1 floors.

If egg does not break, then we are left with 2 eggs and 100-k floors.

Maximum among these 2 choices is the no of droppings required if we begin at that floor.

So, we can find max droppings on each floor and find minimum among them
to arrive programatically at our answer.

Interestingly, this approach works well for any number of eggs.

int maxDroppingsRequired (int numEggs, int numFloors)
{
// With just one egg, we have to test each floor
if (numEggs == 1)
return numFloors;
// For very few floors too, every floor has to be tested
if (numFloors <= 2)
return numFloors;
int minDroppings = -1;
int floorForMinDroppings = -1;
for (int floorK=1; floorK < numFloors; floorK++)
{
int maxDroppingsBelow = maxDroppingsRequired(numEggs-1, floorK-1); // egg broke at floorK
int maxDroppingsAbove = maxDroppingsRequired(numEggs, numFloors-floorK); // egg did not break at floorK
// We have to choose the worst of the cases becuase we do not know
// whether the egg will break or not
int maxDroppingsAtFloorK = Math.max(maxDroppingsBelow, maxDroppingsAbove);
// But we have the freedom to choose that floor for which the above worse-case number is minimum
if (minDroppings == -1 || minDroppings > maxDroppingsAtFloorK)
{
minDroppings = maxDroppingsAtFloorK;
floorForMinDroppings = floorK;
}
}
// Add 1 because whatever floor we choose, one egg must be dropped on that floor
return minDroppings + 1;
}

It's easy to spot in the above that it is very much suited to dynamic programming.

Lookup table can be made between number of eggs and number of floors.

Dynamic Programming Solution

int maxDropsRequiredDP(int numEggs, int numFloors)
{
int lookup[][] = new int[numEggs+1][numFloors+1];
// For a single egg, Drops required = numFloors
for (int floorsK=0; floorsK<=numFloors; floorsK++)
{
lookup[1][floorsK] = floorsK;
}
// For 0, 1 and 2 floors, no of Drops is fixed as well
// regardless of the number of eggs
for (int eggsK=1; eggsK<=numEggs; eggsK++)
{
lookup[eggsK][0] = 0; // For 0 floors, 0 Drops
lookup[eggsK][1] = 1; // For 1 floor, 1 Drop
lookup[eggsK][2] = 2; // For 2 floors, 2 Drops
}
for (int eggsK=2; eggsK<=numEggs; eggsK++)
{
for (int floorsK=3; floorsK<=numFloors; floorsK++)
{
int minDrops = -1;
for (int x=1; x<=floorsK; x++)
{
int maxDropsAtFloorK = 1 + Math.max(
lookup[eggsK-1][x-1],
lookup[eggsK][floorsK-x]
);
if (minDrops == -1 || minDrops > maxDropsAtFloorK)
{
minDrops = maxDropsAtFloorK;
lookup[eggsK][floorsK] = minDrops;
}
}
}
printLookup (lookup);
}
return lookup[numEggs][numFloors];
}
void printLookup(int[][] lookup)
{
System.out.println ();
for (int i=0; i<lookup.length; i++)
{
for (int j=0; j<lookup[i].length; j++)
{
System.out.print (String.format("%3d", lookup[i][j]));
}
System.out.println();
}
}

One of the most important things to note above is that there are a total of 3 loops, one
iterating on eggs and other 2 loops iterating on floors.

The innermost loops is required to find minDrops for floorK

To find minDrops for any floor, we have to find maxDrops on all it's
lower floors and choose minimum among them.

So outer 2 loops find min-Drops for all eggs and all floors, while the
innermost loop has to find maxDrops on each floor so that we can
choose minimum among them.

The above solution used tabulation approach.

However, memoization solution is much easier to visualize as it mimics the
recursive solution very closely (by just saving result in lookup
table at the end of each recursive call and using this lookup table
before beginning recursion).

Memoization
solution is as follows:

Got a thought to share or found a bug in the code? We'd love to hear from you: