Egg Dropping Puzzle

You are given A eggs, and you have access to a building with B floors from 1 to B.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor C with 0 <= C <= B  such that any egg dropped at a floor higher than C will break, and any egg dropped at or below floor C will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= B). 

Your goal is to know with certainty what the value of C is.

What is the minimum number of moves that you need to know with certainty what C is, regardless of the initial value of C?

Examples:

Input: A = 1, B = 2
Output: 2
Explanation:

• Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
• Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.

 If it didn’t break, then we know with certainty F = 2.

•  Hence, we needed 2 moves in the worst case to know what F is with certainty.

Input:  A = 2, B = 10

Output: 4

Approach 1: Brute Force(Recursion)

The basic idea is, we have to find the minimum number of attempts to find the floor i.e. above that floor the egg will break and below that  floor the egg will not break

So, there are two choices

• Egg will break
• Egg will not break

 For Case 1:

• If the egg will break from a particular floor, go further below that floor.

For Case 2:

•  For the second case if the egg will not break from a particular floor then we have to go

             above to find the threshold floor.

Base Conditions:

Algorithm :
 

• Handle the base cases, when floors = 0 or 1 and eggs = 1.
• Run a loop from 1 to K and for each iteration, recurse for the case, if the egg breaks on the Xth floor or not and maximize it.
• Also, minimize the minimum floor found so far.
• Return the minimum floor.

Implementation of the Approach:

C++ Code

int max(int a, int b) {
  return (a > b) ? a : b;
}
int eggDrop(int n, int k) {
  if (k == 1 || k == 0)
    return k;
 
  if (n == 1)
    return k;
 
  int min = INT_MAX, x, res;
  for (x = 1; x <= k; x++) {
    res = max(
      eggDrop(n - 1, x - 1),
      eggDrop(n, k - x));
    if (res < min)
      min = res;
  }
 
  return min + 1;
}

Java Code

static int eggDrop(int n, int k) {
  if (k == 1 || k == 0)
    return k;
 
  if (n == 1)
    return k;
 
  int min = Integer.MAX_VALUE;
  int x, res;
  for (x = 1; x <= k; x++) {
    res = Math.max(eggDrop(n - 1, x - 1),
      eggDrop(n, k - x));
    if (res < min)
      min = res;
  }
 
  return min + 1;
}

Python Code

import sys
 
 
def eggDrop(n, k):
    if k == 1 or k == 0:
        return k
 
    if n == 1:
        return k
 
    min = sys.maxsize
    for x in range(1, k + 1):
 
        res = max(eggDrop(n - 1, x - 1), eggDrop(n, k - x))
        if res < min:
            min = res
 
    return min + 1

Time Complexity: O(2^K), where K is total floors.

Space Complexity: O(1), as no extra space is used

Approach 2: Dynamic Programming(Bottom up)

If you observe clearly, in the above recursive approach, there are overlapping sub-problems. 

In the above image, E(2, 2) is being calculated twice, which can be stored in some table and can be retrieved in O(1).

Let us understand the dynamic programming approach with an example.


Let N = 3 and K = 6, i.e. there are 3 eggs and 6 floors.

Considering the base cases first as described above:

The recursive equation can be defined as :

F(N,K) =  1+min{max( F(N-1,K – 1) , F(N, f – K) ) , k in 1:f}

 Using the above equation, the following table has been filled:

Algorithm :
 

• Initialise an 2D array eggfloor with size (N + 1) X (K + 1).
• Fill the first two columns of the table using the base cases as described.
• Run a loop from i = 2 to N and a nested loop from j = 2 to K. For each jth iteration, run a loop from x from 1 till j:
  • Find the max of eggfloor[i – 1][x – 1] and eggfloor[i][j – x].
  • Minimise the value of eggfloor[i][j].
• Return the value of eggfloor[n][k].

Implementation of the Approach:

C++ Code

int eggDrop(int n, int k) {
  int eggFloor[n + 1][k + 1];
  int res;
  int i, j, x;
  for (i = 1; i <= n; i++) {
    eggFloor[i][1] = 1;
    eggFloor[i][0] = 0;
  }
  for (j = 1; j <= k; j++)
    eggFloor[1][j] = j;
 
  for (i = 2; i <= n; i++) {
    for (j = 2; j <= k; j++) {
      eggFloor[i][j] = INT_MAX;
      for (x = 1; x <= j; x++) {
        res = 1 + max(
          eggFloor[i - 1][x - 1],
          eggFloor[i][j - x]);
        if (res < eggFloor[i][j])
          eggFloor[i][j] = res;
      }
    }
  }
  return eggFloor[n][k];
}

Java Code

static int eggDrop(int n, int k) {
  int eggFloor[][] = new int[n + 1][k + 1];
  int res;
  int i, j, x;
 
  for (i = 1; i <= n; i++) {
    eggFloor[i][1] = 1;
    eggFloor[i][0] = 0;
  }
 
  for (j = 1; j <= k; j++)
    eggFloor[1][j] = j;
 
  for (i = 2; i <= n; i++) {
    for (j = 2; j <= k; j++) {
      eggFloor[i][j] = Integer.MAX_VALUE;
      for (x = 1; x <= j; x++) {
        res = 1 + max(
          eggFloor[i - 1][x - 1],
          eggFloor[i][j - x]);
        if (res < eggFloor[i][j])
          eggFloor[i][j] = res;
      }
    }
  }
  return eggFloor[n][k];
}

Python Code

INT_MAX = 32767
 
 
def eggDrop(n, k):
    eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
 
    for i in range(1, n + 1):
        eggFloor[i][1] = 1
        eggFloor[i][0] = 0
 
    for j in range(1, k + 1):
        eggFloor[1][j] = j
 
    for i in range(2, n + 1):
        for j in range(2, k + 1):
            eggFloor[i][j] = INT_MAX
            for x in range(1, j + 1):
                res = 1 + max(eggFloor[i - 1][x - 1], eggFloor[i][j - x])
                if res < eggFloor[i][j]:
                    eggFloor[i][j] = res
 
    return eggFloor[n][k]

Time Complexity: O(N * K^2), where N is total eggs and K is the number of floors.

Space Complexity: O(N*K), as dp array is used.

Practice Questions:

Egg Drop Problem

FAQ

• What are the special cases for the egg dropping puzzle?
  There are mainly two special cases for the egg dropping puzzle-
  1. If K = 0 or K = 1, the answer is K.
  2. If N = 1, the answer is K.

• What is the efficient approach to solve the egg dropping puzzle?
  The dynamic programming approach is the most efficient approach to solve the problem. The time complexity is O(N*K^2) and space complexity is O(N*K).