43 Egg Dropping Problem Recursive

Egg Dropping using Recursion
Problem statement: You are given N floor and K eggs. You have to minimize the number of times you have to drop the eggs to find the critical floor where critical floor means the floor beyond which eggs start to break. Assumptions of the problem:

If egg breaks at ith floor then it also breaks at all greater floors.
If egg does not break at ith floor then it does not break at all lower floors.
Unbroken egg can be used again.
Note: You have to find minimum trials required to find the critical floor not the critical floor.

Example:
Input:
4
2

Output:
Number of trials when number of eggs is 2 and number of floors is 4: 3

------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:

PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.

[prabhatpandey]

It is very important to understand why we are sending (f-k) in case of egg didn't break and again
using a for loop where k is initiated from 1 again.

the reason is we are checking for a range where we are min number of possibly attempt where egg didn't break.

Let's say in simple terms there are 10 floor.
Egg didn't break from 7th floor. So now only 10-7 = 3 floor needs to be checked.
But to check the next 3 floor we need to use a k loop again.
Here k=1 will represent 8th floor.
Here k=2 will represent 9th floor.
Here k=3 will represent 10th floor.

So to answer the initial question, You need to check the min number of attempts in next 3 floors and that is why you are sending (f-k) and k range is (1, f-k)
PS. I was not able to understand for 2 days why we are looping from K=1 again. Putting this explanation out incase someone gets stuck in the same point again.

[kumarsaurabhraj]

Some hints if someone is having a hard time understanding this

We are given with the number of eggs and the number of floors in the building

We have to find the minimum number of attempts to find the critical floor with the given number of eggs (we can have leftover eggs)

If we have only one egg then there is only strategy to keep dropping eggs starting from the bottom till we get to a floor where the egg breaks then we found the critical floor which will be the floor below it

We do not have any facts on where from dropping from a particular floor wheather the egg breaks or not, for every floor the egg may or may not break

We have to find the niminum number of attemps it would take to find the threshold floor in the worst case

What would be best case? We select any floor and drop the egg from it and it does not break and we drop the egg from the floor above it and it does break, then our previous floor will be the critical floor. So in the best case it would take us two attempts and 1 egg to find the critical floor.

Why just testing for in the middle and halving the floor is not necerrily a good solution? Becuase if you have only one egg left then you would have had to make as many attempts as there are floors to find the critical floor.

What we are doing here? Our function returns the minimum number of attempts required to find the critical floor with E eggs and F floor (given in arguments), we dont what would the most optiomal floor to make the first attempt from so we are making attempt from every floor, we also dont know if by dropping from a floor wheather the egg would break or not so we test for both the cases, we recursively call the function for the left over floor and eggs, since we assume the worst possible case here and we do not know if from dropping from a floor wheather the egg will break or not, we check for which situation it would take greater number of attempts to find the critical floor and take that one.

Also since we want the minimum number of attempts to find the critical floor in the worst possible case we take the minimum of the number of attempts required in the worst possible case when the first attempt is made from that fllor and return that as our answer.


Under standing base cases,

When there is only one egg then we would have to make as many attempts are there are floors in the worst case to find the critical floor.

When there is only one floor then we would have to make only one attempt if the egg does not break then its the critical floor and if it does then ground floor is the critical floor, so the number of attempts in this case also would be as many as there are floors.


When we have no eggs then its not possible to find the critical floor.

Wehn there are no floors i.e. 0 floors then the group floor will be the critical floor so the answer would be equal to 0 i.e. number of floors.

[manasvinsharma]

At first, it looks like a problem which can be solved by Binary Search

[visase]

For those who did not get the max and min usage here :
Consider there are 10 floors in total and we got some x eggs to test .
Lets say we are at 8th floor now(Problem would start from the 1st floor but consider that we are at 8th) . Here we have two options .
1. Egg breaks (we are left with x-1 eggs and 7 floors (8th floor is not the critical one so go down by 1 floor)
2. Egg does'nt break ( we are left with x eggs and 2 floors(9, 10 to test) as 8th floor did not break, its waste of time to go down and check other floors as the problem states if the egg doesnt break at one floor it doesnt break on the floors below to it as well ))

Now here comes the critical point to note, floors to test now are
1. 1-7 so total of 7 floors(egg broke)
2. 9-10 so total of 2 floors (egg did not break)

Whom do you think will give the us the answer Max(attempts (7 floors), (2 floors))), obviously 7 will yeild more floors to test (Keep in mind, you have to cover all the floors so go by max).
So that is the reason why we use max(floorsRemainingEggBrokenCase,

And finally here comes the min part :
Now we tested this by dropping the egg at 8th floor, similarly 3rd floor will yeild us an answer, similarly 5th floor will yeild a diff ans and so on ... till n floors
Tats y we return the min(egg drop attempts on all the floors)!

[kirtipurohit]

There are very rare people who teach geniune content on YT without any fake drama or promotion. Wish we have more people like you

[lakshaychawla]

Adi bhai, mujhe 3-4 months ho gye jb maine first time ye DP ki series start ki thi. Uske baad i went through all of different topic series you taught. Even today sometimes i revise such concepts and questions before some interview or so.
Mai dil se shukriya krna chaunga for such great concept building exercises ❤️❤️

and even urge you to make such videos for other concepts as well like backtracking, greedy, graphs etc. People need you👌🏻

[anant]

42 of 50 (84%) done! The concept is explained very nicely.

[Official-tknc]

my 12 years old brother saw this video with me now he can solve egg drop problem conceptually:)

[starc]

max is used since, we have to find guaranteed moves to find the breaking floor, to find gurantee we take worst cases. Nice vdo

[lakshsadhwani]

man you never can explain bad🙈 respect bro for the content you give us, keep growing❤️

[gaunikasrivastava]

This problem is tougher than scramble string problem 😅😅

[anshulgoel]

Some people call this as front partitioning and not MCM and I was always confused whats the damn difference. This video made it super clear. Just a small variant of the same thing.

[bharatnihar]

Bhai maja aagaya explaination dekh k.Baith gya dimag m Best tutorial for this question on YouTube.

[bhargabnath]

bhaiya, I'm sure that you you must be unwell atleast a little bit, I hear your voice and feel like this. How can I show you my respect for you? Thank you so so much bhaiya, like every videos, this too is simply lit. Kudos to your dedication, bhaiya!!! :) :) :)

[rishabhgaurav]

And Can you Please List Down the question at least of the topics which you couldn't upload.
Like
In the first video you mentioned...


Fibonacci(7 questions)
LIS(10 questions)
Kadane's (6 questions)
DP on grid(14)
others(3)

So that I can complete these topics as well.

PS: You have a very good and curated playlist.

[himanshusoni]

For 100% certainty, always consider the combination of your BEST and others' WORST Case.

[yashmittal]

had to watch this video like to 4 to 5 times to properly understand what is the meaning of worstcase but finally understood

[nitianthrive]

Dil se hats off for your explanation 🫡🫡

[chhaviagarwal]

Loved your way of teaching..Can you please upload videos for remaining topics like kadane's algo and Longest Increasing Subsequence🙏🙏

[ahishnar]

If someone is not able to understand the problem itself then read below explanation.

Here in this problem we have to find the minimum attempts required to find the threshold floor in worst case.
For finding this on every step of recursion we have to find one floor or such a floor from which if we drop an egg then we would be required a minimum attempts overall to find threshold floor overall. And if we follow this concept which I just explained on every recursion step till vase case get hit then with magic of recursion we will automatically get most optimized approach in worst case.
e.g.
Let's say we have 5 floors as
5 4 3 2 1
Then in for loop we have to check one floor or such a floor from which if we drop an egg then we overall we would get minimum attempts.
So in for loop first we will check for 5 then check for 4 then for 3, 2, 1 and at then end as we required minimum number of attempts so in for loop after finding for was floor that is after assuming each floor as the first floor to drop from, we will take or we will pick that floor from which if we drop an egg then we required minimum attempts.
And so in for loop we use min function.
Now the second thing is after dropping an egg 2 things can happen, either egg will break or not break.
If egg breaks then we will go down to check and if egg does not break then we will go up to check.
Now as we need minimum attempts in worst case, concentrate here I am saying in worst case we required minimum attempts and so as we are checking for worst case then egg breaking can be the worst case or egg not breaking can be the worst case. But we do not know which is the worst case and so we are cheking for both the cases.
And so we have to take or use max function here so that we can catch the worst case. And that is why while calling egg break and not break recursion calls which are below the current floor and above the current floor respectively we have to use max function.

So in short on every step of recursion out of all the floors we have to find one floor or such a floor from which if we drop an egg then we would required minimum attempts.

I hope this helps :)