Plz explain how to solve this problem and why do we take max of the two options and then their minimum…
Don’t forward the geeks for geeks link…I want to understand the logic behind max and min…
Egg drop problem
reply at the earliest…
Hey, we try to break the egg the from every floor and there are two condition now:
1.Egg breaks then we are left with a less floor and only floor less than current one.
2.Egg doesn’t breaks then we are left with floor greater than current one.
We take the maximum of the two as we are talking about worst case.We don’t know whether egg will break or not.So,we take the maximum of two saying that in worst case it will take this much trial.
We take minimum of all floors but we can’t take minimum of break and not break situation as it is not upto us to know that egg will break or not.
how to print the max ans of each floor in code after which we consider min ??
plz reply along with code…
reply at the earliest…
Hey,for that drop every egg from every floor.
Create a two array dp[n][k]: where n is number of floor and k is egg.
for every floor,try to break every egg from that floor and take the maximum of the two cases-
a)egg breaks
b)egg doesn’t break
Now,return the dp[n][k]
For code see this link:
How to print for every floor ??like I want to print what shall be worst case for floor 1 floor 2 etc out of which we take minimum…
In the link shared by u we return the final ans only…
for every floor,try to break every egg from that floor and take the maximum of the two cases-
a)egg breaks
b)egg doesn’t break
How to print this so that I can verify my and for each floor…??
Reply at the earliest…
Why are u not replying plz reply fast
Dp[i][k] has the answer for ith floor and k eggs.So just print for the floor you want to print
for example if we have 2 eggs and 4 floors and if i print
dp[1][4] it gives 2…
whereas it should be 4 …
why is that so??
my logic::
option 1:if egg breaks at 1 floor then we get our ans .
option 2 :if egg doesnt break then we need to check for remaining floors and that should give total 4 attempts…
so worst case ans for floor 1 should be 4…
ALSO tell how to print critical floor as well…
Reply at the earliest it’s been 4 days already
Atleast clear my doubt properly…
Why are u not replying to my doubt??plz solve it properly otherwise I will have to take up the matter with coding blocks that ta is not responding to doubts even after 5 days
Why are u not replying??
You might be taking base cases wrong if you have just one egg then ans is always equal to number of floor. Since you will try to break egg from each floor in worst case
You cannot calculate critical floor. Since we have taken just an assumption that egg will break or not from a floor. It is not sure what will the cricitical floor be. You can just find number of ways to find the critical floor in min steps
https://www.includehelp.com/algorithms/egg-dropping-problem-using-dynamic-programming.aspx
plz look at the example given on this site and its explaination…
input 1:
eggs =2,floors=4
Explanation of the problem:
For the Input 1,
Case 1. Drop at first floor:
-
Egg does not break:
If egg does not break then we have three floors left and two eggs. We can either choose 2nd or 3rd floor and proceed similarly but we can easily see we have to do atleast 3 trials. -
Egg breaks:
If egg breaks then we found the critical floor in only 1 trial.
In case 1, the worst possibility is that egg does not break so trials will be 3 for case 1.
Case 2. Drop at second floor:
-
Egg breaks:
We are left with one egg and we have to check only 1 floor so number of trials 2. -
Egg does not break:
We still have two eggs and two floors to check we have to check one by one on these floors so trials needed are 3.
So for case 2 together the worst possibility is 3.
In the end we have to find the minimum of case 1, case 2, case 3, case 4.
this explaination shows that for floor 1 trials are 3 …
i want this to get printed …
explain me how to do so…
I don’t think that can be printed using dp.
For that you have to apply recursion and backtracking.
If you want trials for a particular floor and particular egg combination then you can get it using states stored in dp array
if we have to apply recursion and backtracking then plz provide its code…
input 1:
eggs =2,floors=4
Explanation of the problem:
For the Input 1,
Case 1. Drop at first floor:
-
Egg does not break:
doubt part:(
If egg does not break then we have three floors left and two eggs. We can either choose 2nd or 3rd floor and proceed similarly but we can easily see we have to do atleast 3 trials.) -
Egg breaks:
If egg breaks then we found the critical floor in only 1 trial.
In case 1, the worst possibility is that egg does not break so trials will be 3 for case 1.
in the portion marked as doubt part if egg doesnt break at first floor and then we try at second floor and if egg doesnt break then again 3 floor and again egg doesnt break then we check for 4 floor as well and if egg still doesnt break (no guarantee that egg will break at last floor given in problem) then we should need 4 trials in worst case …but in explaination it is given 3?? explain me this …
Plz reply at the earliest