Super Egg drop problem

Egg dropping problem goes like given n eggs and f floors, our task is to find the minimum number of trials required to find the highest floor from which it is safe to drop eggs (i.e. the eggs don’t break) considering worst-case scenario and a few conditions:

  • An egg can be reused only if it survives the fall
  • If an egg breaks from the xth floor, it will also break from all floors above it (x+1th floor to fth floor)
  • If an egg survives a fall from the xth floor, it will also survive the falling from all floors below it (1st floor to x-1th floor)

A couple of variations of this problem where the number of eggs and the number of floors is fixed are famous puzzles like 2 eggs and 100 floors puzzle or 2 eggs and 36 floors puzzle. Finding solutions to such puzzles take a more mathematical approach.

Solution
Let’s say we have 1 egg and 4 floors and we need to find the minimum number of trials required to determine the highest floor from which it is safe to drop eggs. In this case, if we try to drop the egg from a random floor, it might break and we would not be able to conduct further trials to find the required floor.
Hence in such a case, we have to be careful and start from the 1st floor and keep checking on each floor above, as soon as the egg breaks on a floor, we would have found the required floor.

In this example let’s say starting from the 1st floor and reaching the 3rd floor (f-1thth floor) we still couldn’t determine the required floor, only after the trial on the 4th floor, we would find the answer. Hence in the worst case, we require 4 trials.

Now instead of 1 egg if we have 2 eggs and 4 floors, will it reduce the minimum number of trials required? As we have an extra egg we can afford to start from any floor.
If we start from the 4th floor, the egg might break or it might not –

  • If it doesn’t break we can say that it won’t break on any of the lower floors and hence we were lucky enough to have found the answer in the first trial itself.
  • If the egg breaks, we now have 1 egg fewer, but we also know the 4th floor is not the required floors and hence we would perform further trials on floors below it only.
  • But now since we have just 1 egg, we again have to be careful and fall back to the strategy of starting trials on the 1st floor and checking each floor one by one until the 3rd floor. Again in the worst case, we will check each floor from 1st to 3rd and in this way, we will need 3 trials for that.

So in total, we need (1 trial on 4th floor) + (3 trials from 1st to 3rd floor) = 4 trials if we start trials from the 4th floor. Also note in this case the worse of the two possibilities is 4 and we will consider the worst-case scenario always.

But what if we choose some other floor?

If we start from the 3rd floor, the egg might break or it might not –

  • If it doesn’t break, we now have to perform trials on floors above the 3rd floor. In this case, there’s only one floor above: 4th floor and we have two eggs. When we have just one floor to check we just have to drop an egg from it and we can determine our answer from just that one trial.
  • So in total we will have to do 2 trials = (1 trial on 3rd floor) + (1 trial on floors above it i.e. 4th floor).

  • If the egg breaks, we now have 1 egg fewer, but we also know that the 3rd floor is not the required floors and even floors above it will also give the same outcomes, and hence we would perform further trials on floors below it only.
  • Now since we have just 1 egg, we again have to be careful and fall back to the strategy of starting trials on the 1st floor and checking each floor one by one until the 2nd floor. Again in the worst case, we will check each floor from 1st to 2nd and in this way, we will need 2 trials for that.

So in total, we need (1 trial on 3rd floor) + (2 trials from 1st to 2nd floor) = 3 trials if we start trials from the 3rd floor. Also note in this case the worse of the two possibilities is 3 and we will consider the worst-case scenario always.

Similarly, we will start trials from 2nd floor –

  • If the egg breaks on the 2nd floor, we just have to check the 1st floor. Hence total trials required are: 2
  • If the egg doesn’t break, then we have to check for the floors above that are 3rd and 4th floor, i.e. we have 2 eggs and 2 floors for trials.

Note that we do not care about which floor we are or we’ll be (either floor above us or below) doing trials on, after the current trial we just consider which direction will we do next trials and how many floors remaining (either ground or terrace) so that we can calculate the number of required trials accordingly.

Using this similar approach we can find that with 2 eggs and 2 floors we’ll need 2 trials in the worst case. Hence total trials required are: (1 trial on 2nd floor) + (2 trials on 2 floors above 2nd floor) = 3 trials.

Also note in this case the worse of the two possibilities is 3 and we will consider the worst-case scenario always.

Similarly when we start trials from 1st floor-

  • If the egg breaks on the 1st floor, we don’t need more trials as we know there’s no safe floor. Hence total trials required are 1.
  • If the egg doesn’t break, then we have to check for the floors above that are 2nd, 3rd and 4th floor, i.e. we have 2 eggs and 3 floors for trials.

Using this similar approach we can find that with 2 eggs and 3 floors we’ll need 2 trials in the worst case. Hence total trials required are: (1 trial on 1st floor) + (2 trials on 3 floors above 1st floor) = 3 trials. The worse of the two possibilities is 3.

So we tried on all 4 floors: except for starting from the 4th floor all others require 3 trials to find the required answer. So our answer for min_total_trials(2 eggs, 4 floors): 3.

Considering the above simulation and our approach we can, in general, say that when we conduct a trial at xth floor, there are two possible outcomes:

The egg breaks or it does not break

In both cases, we have to conduct more trials, but in case if egg breaks at xth floor, we need to conduct trials on floors below x and in case if the egg does not break at xth floor we need to conduct trials on floors above x. Only exceptions to “conducting more trials” statement are:

  • When we are doing a trial on the 1st floor and the egg breaks, we don’t need more trials as we now know that there are no safe floors.
  • When we are doing a trial at the fth floor (i.e. highest floor) and the egg doesn’t break, we don’t need more trials as we now know that all floors are safe.

And obviously, if we run out of eggs, no more trials can be conducted.

Note that while conducting a trial at any floor we need to consider the worst possible scenario meaning that we cannot make assumptions about the outcomes of the trial conducted and we have to consider the worse of the two.
Also from our approach in the above example, one can observe that we have to think less about finding the highest safe floor and more about minimizing the number of trials. We actually don’t have to find the highest safe floor but have to focus on minimizing the number of trials by simulating drops from different floors.

We’ll consider doing trials on all the floors and take the worst case for every floor and find our final answer by getting the minimum of all the trials from all floors we just calculated. We aim to reduce our current problem to sub-problems. This shows this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of sub-problems).

Also, we can derive a formula for our finalized approach that will give us the minimum number of trials required to find the highest safe floor given n eggs and f floors:

min_total_trials(n, f) = 1 + MIN( MAX(min_total_trials(n-1, x-1), min_total_trials(n, f – x) ) for each x in {1…f} )

We conduct trials on each floor from 1 to f and for each trial, we consider worse (MAX) of the two possible outcomes, and of all those we consider the one that is minimum. You must have observed in our simulation that we added 1 to the outcome from the sub-problem that was for each of the trials that were done on the current floor, that’s the same 1 that we can see in the formula here.

Using this formula and the exceptions for “conducting more trials” described above as base cases we write a recursive implementation:

int min_total_trials(int e, int f)
{
     /* for 0 floors no trials are required
         for 1 floor only 1 trial is required
        if only 1 egg is available then we have to be 
        careful and perform trials on each of the f floors, 
        hence f trials
     */
   if (f == 0 || f == 1 || e == 1) return f;
   int min_trials = INT_MAX, current_floor_min_trials;
   for (int current_floor = 1 ; current_floor <= f ; ++current_floor)
   {	
      current_floor_min_trials = 1 + 
                max( min_total_trials(e-1, current_floor-1), 
                min_total_trials(e, f - current_floor) );
       min_trials = min(min_trials, current_floor_min_trials); 
   }
   return min_trials;
}
 
int main(void) 
{
    int e = 2, f = 4;
    int min_trials = min_total_trials(e, f);
    printf("%d", min_trials);
    return 0;
}
package com.company;
import java.io.*;
 
class MinTrials
{
    static int max(int a, int b) { return (a > b)? a: b; } 
    static int min(int a, int b) { return (a < b)? a: b; } 
    
    static int min_total_trials(int e, int f)
    {
         /* for 0 floors no trials are required
            for 1 floor only 1 trial is required
            if only 1 egg is available then we have to 
            be careful and perform trials on each of
            the f floors, hence f trials
         */
        if (f == 0 || f == 1 || e == 1) return f;
       int min_trials = Integer.MAX_VALUE, current_floor_min_trials;
       for (int current_floor = 1 ; current_floor <= f ; ++current_floor)
       {
          current_floor_min_trials = 1 
                 + max( min_total_trials(e-1, current_floor-1), 
                        min_total_trials(e, f - current_floor) );
           min_trials = min(min_trials, current_floor_min_trials); 
       }
       return min_trials;
    }
 
	public static void main (String[] args) 
	{
		int e = 2, f = 4;
        System.out.println(min_total_trials(e, f));
    }
}

This implementation takes more than 3 secs for e = 2 and f = 28, and the execution time increases exponentially with increasing inputs.
To find the reason behind such high runtime let’s have a look at the recursive function call tree:
egg drop problem dynamic programming

As we can see while calculating min_total_trials(2,4), min_total_trials(2,2) and min_total_trials(2,2) are calculated repeated.
This means recursive solution solves the same sub-problem over and over rather than always generating new sub-problems. These are called overlapping sub-problems.
As the two properties required for using Dynamic Programming: optimal substructure and overlapping sub-problems hold, we can use dynamic programming for this problem.
Let’s look at the DP solution for this problem: We’ll use a 2D array / DP table to store solutions to the sub-problems and reuse it when required. In DP when moving from bottom-up we will find a solution for each of the sub-problems where-

e = 1 and f = 1, e = 1 and f = 2, e = 1 and f = 3,….. e = 1 and f = F
e = 2 and f = 1, e = 2 and f = 2, e = 2 and f = 3,….. e = 2 and f = F
.
.
.
e = E and f = 1, e = E and f = 2, e = E and f = 3,…… e = E and f = F

DP_table[E][F] will give the final answer for ‘E’ eggs and ‘F’ floors.

int min_total_trials(int e, int f)
{
    int DP_table[e+1][f+1] = {};
     for(int i=1; i<=e; ++i)
    {
         /* for 0 floors no trials are required */
         DP_table[i][0] = 0; 
         /* for 1 floor only 1 trial is required */    
         DP_table[i][1] = 1;    
    }
     for(int i=1; i <= f; ++i)
    {
          /* if only 1 egg is available then we have to 
          be careful and perform trials on each of 
         the f floors, hence f trials */
         DP_table[1][i] = i;
    }
 
     for(int i=2; i <= e; ++i)
    {
          for(int j=2; j <= f; ++j)
         {
             int min_trials = INT_MAX, current_floor_min_trials;
             for (int current_floor=1 ; current_floor<=j; ++current_floor)
             {
                  current_floor_min_trials = 1 
                        + max( DP_table[i-1][current_floor-1], 
                               DP_table[i][j - current_floor] );
                 min_trials = min(min_trials, current_floor_min_trials); 
              }
             DP_table[i][j] = min_trials;
         }
    }
    return DP_table[e][f];
}

int main(void) 
{
    int e = 2, f = 100;
    int min_trials = min_total_trials(e, f);
    printf("%d", min_trials);
    return 0;
}

Javacode

package com.company;	
import java.io.*;
 
class MinTrials
{
    static int max(int a, int b) { return (a > b)? a: b; } 
    static int min(int a, int b) { return (a < b)? a: b; } 
    
    static int min_total_trials(int e, int f)
    {
        int DP_table[][] = new int[e+1][f+1];
         for(int i=1; i<=e; ++i)
        {
             DP_table[i][0] = 0;
             DP_table[i][1] = 1;
        }
         for(int i=1; i <= f; ++i)
        {
             DP_table[1][i] = i;
        }
    
         for(int i=2; i <= e; ++i)
        {
              for(int j=2; j <= f; ++j)
             {
                 int min_trials = Integer.MAX_VALUE, current_floor_min_trials;
                 for (int current_floor=1; current_floor<=j; ++current_floor)
                 {
                      current_floor_min_trials = 1 
                         + max( DP_table[i-1][current_floor-1], 
                                DP_table[i][j - current_floor] );
                     min_trials = min(min_trials, current_floor_min_trials); 
                  }
                 DP_table[i][j] = min_trials;
             }
        }
        return DP_table[e][f];
    }
 
      public static void main (String[] args) 
      {
            int n = 2, f = 100;
            System.out.println(min_total_trials(n, f));
    }
}

Time complexity of DP solution is O(n * f * f) Space complexity of DP solution is O(n * f) where n is no. of eggs and f is no. of floors.

Even though this works for small input, above implementation times out when you run it at Leetcode. We need to change our thinking process. What if we do not think floors and eggs together and think differently in terms of moves and the number of eggs. How about we find that give m moves and k eggs, how many floors can we test?

If we have 1 egg and 1 move only, then we can test only 1 floor. Imagine we are at floor at X, and we have k eggs and m moves allowed. If we make a move on floor x, then there are two possibilities, either the egg will break or it will survive. If the egg breaks, then we are left with k-1 eggs and m-1 moves, this means with k eggs and m moves, we cannot find certainly the floor greater than dp[k-1][m-1]+1. If it does not break, then we have m-1 moves, but still, k eggs remaining, then we can test dp[k][m-1] floors.
If the egg doesn’t break, the egg which is still the first one can start its second try from x + (x-1)floor. Because, if the current egg breaks when it is dropped from the x + (x-1) floor, the second egg still has x-2 opportunities and it can still try from x+1 floor to x + (x-2) floor. If the second egg doesn’t break again, the third try can start from x + (x-1) + (x-2) floor. Hence, the DP recurrence comes up as

dp[m][k] = dp[k-1][m-1] + 1 + dp[k][m-1]

Below is the implementation.

    public int superEggDrop(int K, int N) {
        int[][] dp = new int[N + 1][K + 1];
        int m = 0;
        while (dp[m][K] < N) {
            ++m;
            for (int k = 1; k <= K; ++k)
                dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1;
        }
        return m;
    }

This article is contributed by Bhushan Aggrawal. If you would like to contribute, please reach out to us on [email protected]