Egg Dropping Problem - Approach to write the code (Dynamic Programming) | GeeksforGeeks

This video is contributed by Ishant Periwal.

Please Like, Comment and Share the Video among your friends.

Install our Android App:

If you wish, translate into local language and help us reach millions of other geeks:

Follow us on Facebook:

And Twitter:

Also, Subscribe if you haven't already! :)

[GeeksforGeeksVideos]

The functions eggDrop() and eggdrop() are the same, it is a mistype.

[VinodMoorkoth]

Instead of n and k if you use variables name eggs and floors it will be easy to follow, you can also use its singular forms (egg, floor or eg, fl) when you traverse through each item. That way its readable and easier to follow, especially in theses explanatory videos.

[rashim]

You didn't explain it thoroughly but by watching both "Back to Back SDE's video" and this one, the topic is understood far better than watching anyone alone...

[vivekdatta-jp]

good explanation! Got a clear picture of how the problem is actually modelled, specifically, in all the other videos, people are not clearly stating as to what constitutes to an attempt, which makes it very hard to understand the problem in the first place. But you nailed it!

[ayush_shaz]

GeeksForGeeks is the best !!!! I watched a lot of videos here and there but got satisfaction here

[tamaracousineau]

It would be great to have a video that explains the traceback step and how to identifies which floors were attempted and if the eggs broke or not!

[gajendrasonare]

the only video of gfg which i found helpful

[yashugarg]

Best explanation among all of the GFG videos....

[ranjanrohit]

looking for such videos for a long time...thanks and nice one..

[omi]

Best explanation I have seen for this problem

[JuanGomez-uuwf]

MISTAKE (always droop from the middle if you have more than one egg):


There is a fundamental logical MISTAKE and while it does not affect the result, it does simplify the solution when realized. See:

If you have more than one egg, you can start drooping the first egg from any of the N floors. So, you evaluate the cost of dropping from each floor and stay with the floor that yields the minimum cost (min).

But when you think better, that is completely unnecessary: you don't need to evaluate all the floors, because the middle floor will always yield the minimum drooping cost. Always!

Now, depending on N (even or odd), the middle floor might or might not have an equal number of floors above and below. When it does not, you stay with the worst case scenery: solve the problem with more floors (max).

Applying this logic, you eliminate the min operation that evaluates all possible floors (go always with the middle) and the solution to the problem cuts down as follows:



def eggs(N, e):

if e==1:

return N

if N==1:

return 1

mid=math.ceil(N/2)

if (N-mid)>(mid-1):

return eggs(N-mid, e)+1

else:

return eggs(mid-1, e-1)+1



Explanation of the middle selection: Suppose you have 100 floors and just 2 eggs. You droop the first egg from 99: in the best case it does not break and with the remaining egg you scan the only floor left, the floor 100 (the one above you). So the best case is 2 droops! But in the worst case (it did not break), you have to scan 98 floors below you one by one with the only remaining egg. This makes 98 droops for the worst case. Thus, you are risking a lot (too much difference between the best and the worst case, and you don’t know what the case will be). So:



99: 2 (best)-98(worst)

98: 3(best)-97(worst)

97: 4(best)-96(worst)

.

.

4: 4(best)-96(worst)

3: 3(best)-97(worst)

2: 2 (best)-98(worst)



Look! When you go downwards the risk reduces (the difference between best and worst case tends to zero) but, it happens like that also when you go upwards. So, in the middle point the risk will be near zero (depending of N being even or odd). But, in any case, the middle point (as Buddha said) will always be the most neutral or best option to droop any time you have more than one egg (the one with minimum cost).

[kaushiquedhrubo]

the problem here is not every one like you in GFG can explain problems as good as you do....

[TheUmeshjoshi]

By far the best explanation of the problem. Thanks Ishant

[abhi]

I don't understand the problem statement for the case when k>1.
What is counted as an attempt? Say when you have k eggs, and you finish/break k of them, is that counted as an attempt? Or is breaking any egg counted as an attempt, in which case what is the point of k eggs? It is just equivalent to having 1 egg.

[arpitgoyal]

The solutiowas correct but there was an optimization using binary search that can be made . It would reduce the timecomplexity significantly.

[nands]

Where's the article link in description?
(Background music isn't necessary)

[divyamonshari]

please upload more videos on dynamic programming as its most difficult and vast topic...

[vaalarivan_p]

This is n square k. Pls upload nk soln

[rajatmehta]

i liked this videos among all of the gfg videos
good explanation.

[shreyasingh]

how to get the floors at which the trials has been done?