Egg Dropping Puzzle

November 25, 2021

Egg Dropping Puzzle

The egg dropping puzzle problem is a famous problem that requires dynamic programming to solve optimally. It is asked in various coding interview and coding rounds. In this article, we provide a C++ solution with an explanation.

Egg Dropping Puzzle Problem Description

Egg Dropping Puzzle Problem Description

Given n numbers of eggs and a building with k number of floors. The building has a limit up to which if we drop, the egg does not break. We have to determine the minimum number of egg drops required to find the limit in the worst case.

Input

  • Single line input containing two integers n & k.

Output

  • Single integer the required number of egg drops.

 

Egg Dropping Puzzle Problem Solution Explanation

Solution (Top Down):

To build a top-down solution we must follow the following steps –

Break Down the Problem – Consider we have a function F(e,f) which outputs the minimum number of egg drops/attempts with e eggs required to find the limiting floor of a building with f floors. How to breakdown the problem? For every floor k in the building, we have two choices –

  • If the eggs break, then we recursively call for f(e-1,k-1) because we have 1 less egg and since the breaks, we know the required floor must be below it.
  • If the egg doesn’t break, then we recursively call for f(e,f – k) because we have the same number of eggs, and since the egg didn’t break we know our answer must lie above this floor. So, the number of floors above kth floor are f – k.

We will repeat this for k belonging to [ 1 , f ] .(Remember that we have to minimize the number of attempts in the worst case!) Answer for every k is the maximum of the above two options. since we have to minimize our overall answer, we will take the minimum out of every possible answer of every kth floor.

Find the base case –  The base case is the solution to the smallest known problem. The base cases are –

  • If we have 0 number of floors, then we require 0 egg drop to know whether the egg breaks or not.
  • If we have 1 number of floors, then we require 1 egg drop to know whether the egg breaks or not.
  • If we have 1 egg left, then in the worst case the limiting floor should be at the top and to determine it we will keep on throwing the egg from the bottom to top.

Check for optimal substructure and overlapping subproblems – It is easy to see that the problem can be broken down into smaller problems. 

Solution (Bottom Up):

The bottom-up solution is similar to the above. We create a dp table of size (n+1,k+1) and fill the base cases. After filling base cases we fill the table iteratively.

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int memo[N][N];
//Top down (Memoization)
int solve(int eggs, int floors)
{
    /*
        if we have only 0 floors => 0 attempts are required
        if we have only 1 floor => 1 attempt is required
    */
    if (floors == 0 || floors == 1) 
        return floors;

    if (eggs == 1)  // Worst Case for 1 egg is => we start dropping the egg from the bottom
        return floors;

    if (memo[eggs][floors] != –1)
        return memo[eggs][floors];

    int ans = INT_MAX;

    for (int i = 1; i <= floors; i++)
    {
        int op1 = 1 + solve(eggs – 1, i – 1);  // If the egg breaks
        int op2 = 1 + solve(eggs, floors – i); // If the egg doesn’t breaks;
        int curr = max(op1, op2);
        ans = min(ans, curr);
    }

    return memo[eggs][floors] = ans;
}

int bottomUp(int eggs, int floors)
{
    int dp[eggs + 1][floors + 1];

    for (int egg = 1; egg <= eggs; egg++)
    {
        dp[egg][0] = 0; // for 0 floors
        dp[egg][1] = 1; // for 1 floor
    }

    for (int floor = 2; floor <= floors; floor++)
    {
        dp[1][floor] = floor;
    }

    for (int egg = 2; egg <= eggs; egg++)
    {
        for (int floor = 2; floor <= floors; floor++)
        {
            int ans = INT_MAX;

            // Similar to above top down procedure
            for (int i = 1; i <= floor; i++)
            {
                int op1 = 1 + dp[egg – 1][i – 1];
                int op2 = 1 + dp[egg][floor – i];
                int curr = max(op1, op2);
                ans = min(ans, curr);
            }

            dp[egg][floor] = ans;
        }
    }
    return dp[eggs][floors];
}
int main()
{
    memset(memo, –1, sizeof memo);
    int eggs, floors;
    cin >> eggs >> floors;
    cout << solve(eggs, floors) << endl;

    cout << bottomUp(eggs, floors) << endl;
    return 0;
}

Output

3 5
3
3