The Egg Dropping Puzzle is a famous challenge that requires the application of dynamic programming for optimal solution. Below is an illustration of this renowned problem scenario involving N = 2 eggs and a building with K = 36 levels.
Consider the situation where we want to determine which floors in a 36-story building are safe to drop eggs from and which will result in the eggs breaking when they land. We assume the following:
- A fallen egg that survives can be utilized once more.
- A cracked egg needs to be thrown away.
- All eggs experience the same effects of a fall.
- An egg would shatter if it were dropped from a higher floor since eggs break when they are dropped.
- An egg would survive a shorter fall if it can survive a fall.
- Both the possibility that eggs are broken by first-floor windows and the possibility that the 36th floor does not break eggs are not excluded.
There is a single method for testing with only one egg at our disposal, ensuring the desired result. If the egg remains intact after being dropped from the first floor, proceed to drop it from the second-floor window. This process continues incrementally until the egg breaks. In the most unfavorable situation, this strategy may require up to 36 drops.
Determining the critical floor is not the primary concern; instead, the focus lies in determining the optimal floors for dropping eggs to minimize the total number of trials. This article will delve into a universal approach to addressing the challenge of 'N' eggs and 'K' floors.
Approach 1: Egg Dropping Puzzle using Recursion:
- Try dropping an egg from each floor (from 1 to K) to get the minimum number of drops required in the worst-case scenario. A component of the solution will be the floor that provides the least value under the worst-case scenario.
- The worst-case minimum number of trials is returned in the following solutions, and these solutions can be changed to output the trial floor numbers as well.
What is the worst-case scenario?
The individual will definitely reach the lowest floor in the most unfavorable scenario. For example, with only "1" egg and "K" floors, the egg will be thrown from the initial floor repeatedly until it breaks, which is expected to happen on the "Kth" floor. Therefore, the total number of attempts required to ensure this outcome is "K".
Optimal Substructure:
When an egg is released from a specific floor labeled as "x," it may lead to one of two outcomes: either the egg will shatter upon impact or it will remain intact. In the scenario where the egg breaks upon landing from the "xth" floor, it implies that there are floors below "x" where the egg would remain unbroken. Consequently, the task transforms into evaluating x-1 floors with n-1 eggs, as there must be lower floors than "x" where the egg does not break.
Conversely, if the egg remains undamaged after being dropped from the "xth" floor, the problem is then simplified to assessing 'k-x' floors with n eggs. In such a situation, the objective is to examine floors above 'x' to determine the outcome. It is advisable to release an egg from each floor (ranging from 1 to K) to establish the minimum number of drops necessary in the most unfavorable circumstances. A crucial aspect of the solution involves identifying the floor that yields the least value in the worst-case scenario.
We limit our selection to a maximum of two instances to minimize the trial count in the worst-case scenario. Each level is evaluated based on the higher of the two scenarios mentioned, and the choice is made to minimize the number of trials required.
Example:
Let's consider a scenario to demonstrate the Egg Dropping Challenge in C++ through Recursive methods.
#include <bits/stdc++.h>
using namespace std;
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;
}
int main()
{
int n = 3, k = 12;
cout << "Min trials " "in worst case with "<< n << " eggs and " << k << " floors is "<< eggDrop(n, k) << endl;
return 0;
}
Output:
Complexity Analysis:
The program's time complexity is exponential due to the existence of overlapping subproblems.
Auxiliary Space: The spatial complexity is O(1) as no data structure was employed for storing values.
Approach 2: Egg Dropping Puzzle using Dynamic Programming:
This issue exhibits the feature of Overlapping Subproblems as it involves repeated calls to the same subproblems. Consequently, the Egg Dropping Challenge showcases elements typical of a dynamic programming problem. To prevent redundant recalculations of identical subproblems, a temporary array eggFloor is constructed incrementally, following a similar approach used in other well-known Dynamic Programming (DP) challenges.
In a formal manner, when transitioning to the DPi state, where 'i' represents the quantity of eggs and 'j' signifies the count of floors:
For every level 'x', it is necessary to journey from '1' to 'j' and explore a minimum of:
(1 + max( DP[i-1][j-1], DP[i][j-x] )).
Example:
Let's consider a different scenario to demonstrate the Egg Dropping Challenge in C++ through the implementation of Dynamic Programming.
#include <bits/stdc++.h>
using namespace std;
int max(int a, int b) { return (a > b) ? a : b; }
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];
}
int main()
{
int n = 3, k = 25;
cout << "\nMin trials ""in worst case with "<< n << " eggs and " << k << " floors is "<< eggDrop(n, k);
return 0;
}
Output:
Complexity Analysis:
Time Complexity: The computational time required is proportional to the product of N and K squared, denoted as O(N * K^2). This is due to the utilization of a nested for loop that iterates 'K squared' times for each egg.
Auxiliary Space: The time complexity is O(N K) . A two-dimensional array with dimensions nk is employed for storing elements.
Approach 3: Egg Dropping Puzzle using Memoization:
In the initial recursive approach, a two-dimensional dynamic programming table can be employed to store the results of repeated subtasks, aiding in reducing the time complexity from exponential to quadratic.
The state of the dynamic programming table is represented as dpi, where 'i' represents the number of eggs and 'j' represents the number of floors.
Follow the below steps to solve the problem:
- Create a 2-D array memo with the size N+1 * K+1 and then call the solveEggDrop(N, K) function.
- Return memon if memoN has already been calculated.
- Return K if K == 1 or K == 0 (Base Case).
- Return K if N equals 1 (base case).
- Create an integer res and an integer min that are both equal to the integer Maximum.
- From x equal to 1 until x is less than or equal to K, run a for loop. Set res equal to maximum of solveEggDrop(N-1, x-1) or solveEggDrop(N, k-x) If res is less than integer min then set min equal to res
- Set memoN equal to min + 1
- Return min + 1.
- Set res equal to maximum of solveEggDrop(N-1, x-1) or solveEggDrop(N, k-x)
- If res is less than integer min then set min equal to res
Example:
Let's consider another scenario to demonstrate the Egg Dropping Problem in C++ with Memoization.
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
vector<vector<int> > memo(MAX, vector<int>(MAX, -1));
int solveEggDrop(int n, int k)
{
if (memo[n][k] != -1) {
return memo[n][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(solveEggDrop(n - 1, x - 1),solveEggDrop(n, k - x));
if (res < min)
min = res;
}
memo[n][k] = min + 1;
return min + 1;
}
int main()
{
int n = 3, k = 15;
cout << "Min trials ""in worst case with "<< n << " eggs and " << k << " floors is ";
cout << solveEggDrop(n, k);
return 0;
}
Output:
Complexity Analysis:
Time Complexity: O(n*k^2) where n represents the number of eggs and k denotes the number of floors.
Additional memory usage: O(n*k) due to the utilization of a two-dimensional memoization table.
Approach: 4
To solve the problem follow the below concept:
It has previously been explained how to implement a technique with a time complexity of O(N * K^2), where dpN = 1 + max(dpN - 1, dpN) for i in the range of 1 to K. We extensively explored all possibilities within that approach.
dpm represents the highest quantity of levels that can be examined using x eggs and m attempts.
According to the DP equation, we must relocate one space to a floor: dp[m][x] = 1 + dp[m - 1][x - 1] + dp[m - 1][x].
We can check dp[m - 1][x - 1] floors if the egg breaks.
The floors of dp[m - 1][x] can be checked if the egg doesn't crack.
Follow the below steps to solve the problem:
- Declare a 2-D array of size K+1 * N+1 and an integer m equal to zero
- While dpm < k Increase 'm' by 1 and run a for loop from x equal to one till x is less than or equal to n. Set dpm equal to 1 + dpm-1 + dpm-1.
- Return m.
- Increase 'm' by 1 and run a for loop from x equal to one till x is less than or equal to n.
- Set dpm equal to 1 + dpm-1 + dpm-1.
Example:
Let's consider another instance to demonstrate the Egg Dropping Puzzle using C++.
#include <bits/stdc++.h>
using namespace std;
int minTrials(int n, int k)
{
vector<vector<int> > dp(k + 1, vector<int>(n + 1, 0));
int m = 0; // Number of moves
while (dp[m][n] < k) {
m++;
for (int x = 1; x <= n; x++) {
dp[m][x] = 1 + dp[m - 1][x - 1] + dp[m - 1][x];
}
}
return m;
}
int main()
{
int n = 3, k = 39;
cout<<"Min trials " "in worst case with "<< n << " eggs and " << k << " floors is ";
cout << minTrials(2, 36);
return 0;
}
Output:
Complexity Analysis:
Time Complexity: The time complexity is O(N * K).
Auxiliary Space: The space complexity is O(N * K), where N and K represent different variables.
Approach 5: Egg Dropping Puzzle using space-optimized DP:
In this technique, enhancing the approach to 1-D Dynamic Programming is feasible as we solely rely on information from the preceding row to compute the present row of the Dynamic Programming table, without requiring additional data.
To solve the issue, follow the instructions listed below:
- Make a N+1-sized array dp and an integer m.
- Run a for loop from m = 0 to dp[n] k.
- From x equal to n until x is greater than zero, execute a nested for loop.
- dp[x] should be set to 1 + dp[x-1].
- Return m
Example:
Let's consider another scenario to demonstrate the Egg Dropping Puzzle in C++ leveraging space-efficient Dynamic Programming.
#include <bits/stdc++.h>
using namespace std;
int minTrials(int n, int k)
{
int dp[n + 1] = { 0 }, m;
for (m = 0; dp[n] < k; m++) {
for (int x = n; x > 0; x--) {
dp[x] += 1 + dp[x - 1];
}
}
return m;
}
int main()
{
int n = 3, k = 12;
cout<<"Min trials "" in worst case with "<< n << " eggs and " << k << " floors is ";
cout << minTrials(2, 24);
return 0;
}
Output:
Time Complexity: The computational time complexity for this algorithm is proportional to the product of N and the logarithm of K, denoted as (N * log K).
Auxiliary Space: The space complexity is O(N).
