You are given two integers N and K. N represents the number of eggs and K represents the number of floors in a building.
You have to find the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.
The critical floor is defined as the lowest floor from which you drop an egg and it doesn't break.
There are certain which you have to follow -
All eggs are identical.
An egg that survives a fall can be used again.
A broken egg can't be used again.
If the egg doesn't break at a certain floor, it will not break at any floor below.
If the egg breaks at a certain floor, it will break at any floor above.
Understanding the Problem:
If we are given n eggs and k floors of a building and we assume c to be the critical floor, then if an egg is thrown from a floor higher than or equal to c then the egg breaks else it survives.
We have to estimate and return the minimum attempts to find the critical floor.
Approach:
WHAT
We take the following example to understand this question.
A manager at a company can assign a task to either x1 or x2 or x3 or x4. The manager is asked to assign a project P to only one of the given four resources such that it is guaranteed that the work gets done, that too in minimum time.
For the manager, assigning the work to one of the four resources is a choice. But whether the chosen resource gets the work done in little time or a large amount of time is left to the luck of the manager.
Hence, the manager must consider the factor of "luck" against himself.
From this example, we have understood that if in a problem of estimation there is some role of "luck", we optimize our bad luck. This means that we accept that we will have bad luck in all situations and out of all the worst outcomes possible, we incline towards the option with the least bad luck. This option of ours will be the guaranteed best option.
In conclusion, the guaranteed best is the best option out of all the worst options.
In figure 2, we see that assigning the work to one of the resources out of x1, x2, x3 and x4 is the manager's choice.
If each resource can do the work in the given 2 time durations depending on the luck, then we consider the worst case scenario for each resource by taking the maximum of the 2 time durations for each of the resources.
Now we compare all the worst case scenarios and choose the one which seems the best option out of those. That is, we choose the minimum time out of all the maximum times.
So, if we had a situation like figure 4, where all the possible time durations to complete the work are given for each resource, we choose the maximum/ worst case time for each of them.
These worst case durations are 8, 7, 9 and 12. Out of all these worst case times we choose the best option (i.e. minimum time). Hence the answer is 7.
If the above explanation is clear to you then the further discussion of the "egg drop" problem will be easy.
In Figure 5, there are a total of k floors. If we drop an egg from floor 'f' and the egg survives, it means that according to the definition, the critical floor must lie somewhere above the floor 'f'. The floors above the 'f' can be written as (k-f) floors.
Now, let's say e|k denotes "using e eggs, the critical floor out of k floors is to be found".
So, Figure 6 shows if an egg is thrown from 'f' floor, it has 2 options: either it survives or it breaks.
If the egg survives, then we are left with e eggs and need to determine the critical floor from the floors above 'f' floor i.e. (k-f) floors.
Else if the egg breaks, then we are left with (e-1) eggs and need to determine the critical floor from the floors below the floor 'f' i.e. (f-1).
In figure 7, the numbers along the edges represent the floors from which an egg is thrown.
The values xb and xs denote the minimum attempts such that an egg breaks and survives respectively when thrown from the corresponding floor.
For each choice of floor, there can be 2 situations: either the egg breaks or it survives.
Now for each floor, we choose the worst case option, i.e. the option that takes the highest number of attempts.
Now out of the maximum attempts for all the floors, we choose the minimum value of attempts.
Hence our answer will be as shown in figure 8.
We now consider some base cases.
If the total number of floors are 0, then the attempts are 0.
If there is only one floor, then we arrive at our answer in only one attempt.
If we have no eggs, then no attempts or 0 attempts are possible.
If we have only 1 egg, then our worst luck is that the critical floor is not present at any floor. So to reach this conclusion, we need to throw the egg from every floor.
DYNAMIC PROGRAMMING
Reader, after attempting so many problems of dynamic programming you must be well versed with the dp array process.
We quickly make the dp array for the situation when the total number of floors are 7 and the number of eggs are 3.
As we have already discussed in the base cases, if the number of eggs are 0 or the total number of floors are 0 then there can be no attempts. Hence the first row and column are marked 0.
Also, if there is only 1 egg, then for k floors, the attempt will be k and if we have only 1 floor then the attempt is also 1 as shown in figure 11.
Now for 2 eggs, using the formula in figure 6, we make the following tree for the 2nd floor.
According to this tree, the dp array is filled as shown in Figure 12.
Hence, the final value for the cell corresponding to 2 eggs and 2 floors is min+1=1+1=2.
We highly suggest you watch the solution video to understand the filling of dp array better.
Finally the dp array comes out to be as shown below.
The answer is stored in the last cell of the array and equal to 3.
CODE
Reader, you will find the code of this problem very easy if you have understood the approach.
We recommend you to write the code on your own and then refer to the code given below.
import java.io.*;
import java.util.*;
public class Main {
public static int eggDrop(int n, int k){
int[][]dp=new int[n+1][k+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
if(i==1){
dp[i][j]=j;
}else if(j==1){
dp[i][j]=1;
}else{
int min=Integer.MAX_VALUE;
for(int mj=j-1,pj=0;mj>=0;mj--,pj++){
int v1=dp[i][mj]; //egg survives
int v2=dp[i-1][pj]; //egg breaks
int val=Math.max(v1,v2);
min=Math.min(val,min);
}
dp[i][j]=min+1;
}
}
}
return dp[n][k];
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
//n -> number of eggs and k -> number of floors
int n = scn.nextInt();
int k = scn.nextInt();
System.out.println(eggDrop(n,k));
}
}
java;
true";
In case you have any difficulties in understanding the above code, we strongly recommend you to watch its solution video.
Analysis
Time Complexity:
O(n2)
Space Complexity:
O(n2)
We conclude this article here and hope you were able to grasp its concept.
