Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Egg Dropping Problem

The lesson describes the various approaches to solve the egg dropping problem.

We'll cover the following...

Solution #1: Brute force

Let’s start by looking at the brute force solution to this problem:

Java
class EggDropping
{
  public static int eggDrop(int eggs, int floors) 
  {
    // If there are no eggs, then there can't be any tries
    if (eggs <= 0)
      return 0;
    
    // If there are no floors, then no trials needed. OR if there is 
    // one floor, one trial needed.
    if (floors == 1 || floors == 0)
      return floors;
    // We need k trials for one egg and k floors 
    if (eggs == 1)
      return floors;
    int min = Integer.MAX_VALUE;
    int x, res;
    // Consider all droppings from 1st floor to kth floor and 
    // return the minimum of these values plus 1. 
    for (x = 1; x <= floors; x++) {
      res = Math.max(eggDrop(eggs - 1, x - 1), eggDrop(eggs, floors - x));
    if (res < min)
        min = res;
    }
    return min + 1;
  }
 
  public static void main(String args[]) 
  {
    int eggs = 2, floors = 10;
    System.out.println("With " + eggs + " eggs and " + floors + " floors, the minimum number of trials in worst are: " + eggDrop(eggs, floors));
  }
};

Explanation

When we drop an egg from a floor x, there can be two cases:

  • The egg breaks.

  • The egg doesn’t break.

  1. If the egg breaks after dropping it from xth floor, we only need to check for floors lower than x with the remaining eggs; so, the problem reduces to x-1 floors and n-1 eggs (line 24).

  2. If the egg doesn’t break after dropping it from the xth floor, we only need to check for floors higher than x; so, the problem reduces to k-x floors and n eggs (line 24).

Since we need to minimize the number of trials in the worst case, we take the maximum from both cases (line 24). We consider the max of the above two cases for every floor and choose the one which yields the minimum number of trials (lines 25-26).

Solution #2: Memoization

The solution above, even though it is correct, results in redundant recursive calls which can be avoided if the solution is memoized:

Java
class EggDropping
{
  public static int eggDropRec(int eggs, int floors, int [][] lookupTable) 
  {
    // If there are no eggs, then there can't be any tries
    if (eggs <= 0)
      return 0;
    
    // If there are no floors, then no trials needed. OR if there is 
    // one floor, one trial needed.
    if (floors == 1 || floors == 0)
      return floors;
    // We need k trials for one egg and k floors 
    if (eggs == 1)
      return floors;
    
    lookupTable[eggs][floors] = Integer.MAX_VALUE;
    int x, res;
    // Consider all droppings from 1st floor to kth floor and 
    // return the minimum of these values plus 1. 
    for (x = 1; x <= floors; x++) 
    {
      res = 1 + Math.max(eggDropRec(eggs - 1, x - 1, lookupTable), eggDropRec(eggs, floors - x, lookupTable));
      if (res < lookupTable[eggs][floors])
        lookupTable[eggs][floors] = res;
    }
    return lookupTable[eggs][floors];
  }
  public static int eggDrop(int eggs, int floors) 
  {
    int [][] lookupTable;
    lookupTable = new int[eggs + 1][];
    for (int i = 0; i < eggs + 1; i++) {
      lookupTable[i] = new int[floors + 1];
      for (int j = 0; j < floors + 1; j++)
        lookupTable[i][j] = 0;
    }
    return eggDropRec(eggs, floors, lookupTable);
  }
  public static void main(String args[]) 
  {
    int eggs = 2, floors = 10;
    System.out.println("With " + eggs + " eggs and " + floors + " floors, the minimum number of trials in worst case are: " + eggDrop(eggs, floors));
  }
};

Explanation

In the memoized approach, we use a 2-D array, lookupTable ...