Binary search wouldn't be feasible for this problem. If you have less than log(N) eggs, narrowing down to the threshold floor is not always possible. Eg: 100 floors and 2 eggs. Throw the egg on floor 50. Breaks. Throw the egg on floor 25. Breaks. Uh oh... Also, thanks to Banipreet Singh Raheja for pointing out two further optimised solutions here: leetcode.com/problems/super-egg-drop/solution/ Cheers!
I am late but using binary search with another hypothesis(i.e finding no of floors with d attempts and n eggs) can optimize the solution..just type in egg dropping problem Brilliant on google and search for the resource on brilliant website, hope it helps :)
using binomial coefficient and binary search method we can solve it in O(nlog(k)) time. www.geeksforgeeks.org/eggs-dropping-puzzle-binomial-coefficient-and-binary-search-solution/ If possible please explain this.
Thanks for explaining each step with such clarity. I love the way you progress toward the problem as to why and how you are doing what you are doing. Don't trade this part for speed-or-anything. Some other channels really lack this as they are just vomiting out things they have mugged up, not telling why and what of the approach. Keep making such videos. Subscribed for eternity.
You are great man !! Simply great !! Not just spitting out some mugged up or already cooked up stuff., but explaining everything to the core that too in a simple and effective way. Great job. Keep up the good job and enlighten more people like me.
Hi, I got this solution from here brilliant.org/wiki/egg-dropping/ (last para) But a very formal proof is given, then I came up with my own greedy proof and here it is. So, Idea is to maximize the number of floors that we can cover given "t" trials and "e" eggs. Take some examples for clarity: t=3,e=1 answer is 3 (1+1+1) t=5,e=2 answer is 15(5+4+3+2+1) t=14,e=2 answer is 105(15+14+13......2+1) { These answers are inspired by 2 egg puzzle, i.e. given two eggs and "n" floor,find minimum trials eg For n=100 , e=2 answer is 14 as the first trial is at 14 then at 27(14+13) then at 39(14+13+12) and so.... } Here, intuitively we are choosing our first trial as t , such that if egg breaks here then (t-1) must be covered by remaining eggs and further our next trial is at t+t-1 because we have wasted 1 trial at "t" floor, so we can go maximum t-1 more floors ahead and so on... So every time when eggs are 2, the answer is always the minimum value of" x" such that x+(x-1)+(x-2)+...+1 >=n. Also, we can say that for "t" trials, and eggs =2, we can go for (t+1)C2 floors ahead eg t=14, floors=105. So far so good. Now, things get tricky for eggs=3,4,5 Let us try to think in the same direction for eggs=3, Here, we should drop our first egg at a floor "f" such that (f-1) can easily be covered by 2 eggs, then are second drop should be at f+(f-1) floor, using the same analogy. and we already know that the maximum number of floors with 2 eggs and "t" trials are given by (t+1)C2. So, in effect for eggs =3, and "x" trials, we can cover 2C2 + 3C2 + 4C2+...+(x-1)C2 + xC2 = (x+1)C3 floors. Hence , we can follow up the pattern and hence the answer. I hope you may get the essence of it, idea is to maximize the floors by eggs.
You can make improvement in the innermost loop by doing Binary Search instead of linear search which would make Time Complexity of your code to O(n*e*log(n)).
Amazing! With the clarity of concept as well as the underlying mathematics, no wonder you work for directi!(saw that from comments) Seeing your approach of problem solving I was thinking if "this guy is from IIT?" and "that's the way true engineer solves problem!". You have definitely motivated me to go more for problem solving! Please upload more videos whenever you get the time. It would be great to get insights from your approach to problem solving :)
Hey Gaurav, I really like the videos you make. Also, I just wanted to say that whenever you are speaking something I feel like you're going to burst into laughter. 😂 That really makes your videos kinda different in a positive way. :))
At 16:45 , n=2 and e=2 so f[2][2] = max(f[2-1][2],f[1-1][2-1]) , here x =1 f[2][2] = max(f[1][2],f[0][1]) , instead of max(f[1][2],f[1][1]) but now the answer will not be 2 so we have to iterate x to n which will include the case when we drop the egg from the top most floor as well. P.S: Please let me know I am getting something wrong here. :D
I also had the same idea of using binary search. Suppose floors are numbered from 1..10, we drop a egg to floor 5. If it breaks, then we must search from 1..5, else from 6..10. This will be at max O(log2(n))
I read about 100 floors, 2 eggs. Now it is clear why binary search wont work. We only have 2 eggs, if they both break we cannot get the answer. eg for 100 floors, if threshold of egg is 13, we will break egg at floor 50, then at floor 25. We wont have any remaining eggs to test.
My mind was now accepting if egg will be ever safe as if we drop even from a foot high :-) The more realistic object should have been coconut, pumpkin etc ... :-) Anyway idea was good, good explanation.
Hi Gaurav, excellent explanation. My question is: what is the relationship between the first part of the explanation where you showed that the minimum number of tries is 2 times square-root of N and the later part where you proved the generic case with the minimization?
Hi Gaurav, while reaching the end of your video, can you please explain why you took the value of x-1 as 1 in your second function which was F(x-1)(e-1) while you started with x=1. Thanks in advance
Your first analytic solution of Y = (B + N/B) is based on a fixed size of floors within each segment of floors. By minimizing Y you get that B=SQRT(N) For example for N=100, B=10 which tell us that the best attempts are at the lower segment and the top segment suffers from 20 attempts. A better solution will be if we choose, instead, a decreasing size for each segment of floors; For the first trial you go [B] floors but for the next you go only [B-1] and the next will be [B-2], ..., [B-B] By having decreasing sizes, the maximum trials for each segment is now fixed [B], [B-1+1], [B-2+2] ... [B]. The sum of these variable size segment is [B+0] + [B-1]+[B-2]....+[B-B] = 0.5*B^2 = N and therefore; The optimal initial size B=SQRT(2)*SQRT(N) For example if N=100 --> B=14
+Rbi Pro Thats correct, and that is what the solution uses for egg size 2. In fact, recursively, we are looking at segments which can be completed using 1 egg less and one turn less everytime we have to make a throw. Maybe a direct formula can be found for f(n,e), but I don't know it :-p
@Gaurav , your second F[x-1][e-1] says to consider x-1 floors for e-1 eggs. But in your example f[2][2] this will amount to F[0][1] which I didn't understand why you missed ? Can you clarify this .
When I started learning programming , I loved Java a lot, but there was no one in my college to guide me. Even I remember geeksforgeeks don't use to have its maximum codes in java those days. So, even wanting to do those things, I couldn't do them. Even if I wanted to do them in Java myself I was not sure about if my solution is correct or not. Now coders like you guys make life of people like us great. You guys are really trying your best to promote the coding culture among college graduates. Hope to contribute like you guys one day. Good work Gaurav, keep sharing the knowledge. At least I don't have to bother to learn DS Algo now. It might be little late than usual for learning them but definitely its not over.
For those wondering, the min. number of tries taken in the last example (when n=8) is 4 ( th-cam.com/video/o_AJ3VWQMzA/w-d-xo.html ), while in the 2nd (minimization using derivative) case, it would be = 2*sqrt(8) = 2 * sqrt(4 * 2) = 2 * 2 * sqrt(2) = 4 * 1.41, which is greater than 4. #IDoNotKnowWhyIPostedThis?
First of all ,Thank you for sharing knowledge. I have a doubt. Why are we not throwing egg from the last floor , for example if n=5 from 5th floor? Please correct me if i have misunderstood something.
Great explanation! However I am doubtful about the solution B = root(N) (at time 5:41 in the video). I think it was for the case of 2 eggs. For two eggs and 100 floors problem it would give number of tries as 20 but the answer is 14.
Another solutions, try from 1st, then 2nd floor, then 4th floor, then 8th foor, then 16th floor so on. Basically 2 power n growth every time, Then when it breaks use binary search between that number and last number that doesn't break it
That won't be optimal though. The number of tries could be as large as log(n) + log(n/2) + log(n/4) = log(n) + log(n) - 1 + log(n) - 2 + log(n) - 3 + ... + 1 = log(n)^2 / 2 Try the approach for 100 floors. It's more than 14 tries.
Hello@@gkcs thanks for replying. Lets assume that our floors are a power 2. So lets assumed this apartment has 128 floors. So now if I jump starting from 0 all the way till 128 in powers of 2. I will be attempting from these floors = [1 2 4 8 16 32 64 128] So if worst case scenario I realize that my egg breaks for the first time on the top floor only. That means the egg breaks somewhere between 64-128 floors. That means If I do Binary search between these numbers my worst case scenario Big O will be log(2^(n-1)) where n is 7 here (2^7 = 128). This is worst case complexity. Avg case will be less than this right. So are you saying its bad because log of a exponential number is being done here? If that's the case maybe we can use this approach and then divide this part with your block approach. My intent is if n is large like a million, I will find the range quicker with exponential jumps. Please tell if I am wrong somewhere?
@@prabhatracherla3098 take your time and think it through. Can you binary search after breaking an egg at 128? No. What if you break the second egg at midpoint? You have no more eggs to search with. If you do a linear search after it breaks at 128, you have reduced the size to 64-128. That's N/2 tries worst case. Pretty bad. The approaches here are O(sqrt(n)) and better.
Thanks for the video! I really enjoy the way you explain things. It is very nice to see the dynamic programming approach to the egg dropping problem. I think though that your logic has a mistake. I implement your algorithm and it gives wrong results. For example it produces F[10,2]=4 instead of 5. In fact, the path predicted if the first two attempts do not break the egg is floors 3 and 6 (which is the correct answer by the way), but then we are left with two eggs and 4 floors to check (7, 8, 9 and 10), which requires a minimum of 3 attempts, so 5 in total. I think that I have pinpointed the mistake at your logic. This problem is kindof special over other dynamic programming problems in the sense that we cannot perform the operations in any order we like. The first steps can be done only in increasing order of floors. When you split the building to bottom and top parts, you ignore this fact and you just add 1 attempt for floor x. This is true for the bottom part of the building, as you are going to treat all its floors in the recursion. For the top part of the building though, this is not true. Your assumption that you reached x with a single attempt is not correct, so for this case you have to add an extra number of attempts, which have been already performed at the bottom part, to reach x. I think this number is int((x-1)/((2**e)-1) but I might be wrong. Thanks again for the video.
@@gkcs I tried the code. It's what I have understood from the video, and it has the bug I mentioned. For F[10][2] it gives 4. To convince yourself that it is wrong just take the F[100][2]=14 result. There is no way to check 100 floors with 14 tries, by just using 2 eggs. I think what you need to do to fix it is to change your line 23 to: final int EggSurvivedResult = results[i - x][j] + (x-1)/((int)Math.pow(2, j)-1);
@@gkcs OK... I'm wrong :( Sorry for that. It was my misinterpretation of the DP algorithm results when I was trying to derive the non-DP solution. I lead myself to a different solution, which is not the optimal one, so I modified your algorithm to reach to it. Now I understand better the results of your algorithm, which are correct. At least with two eggs, the problem F[10][2] is indeed 4, and it means start dropping the egg from the 4th floor (not the 3rd as I mentioned earlier) and then move to the 7th (decrease the step by 1). This leads to worst case scenario of 4. The same is true for the F[100][2], which is 14 with the same logic (start dropping at 14th, then 27th, etc, ending up with up to 14 attempts). I will now try to understand the results for eggs>2.
shouldn't the worst number of tries be (N/B) + B - 1? That makes it equal to (2 * sqrt(N)) - 1 worst tries. Doesn't affect the differentiation though. Good video, Thanks!
fastest case answer throw from the first floor (if i am the owner of first floor) possibility if it breaks then threshold floor is first floor, if it doesnt break then definitely threshold floor is the second floor because second floor owner will definitely break it by throwing it into someones head
I know it's quite late but I must comment. Got to keep the patience to understand this but really nice work done here. especially deriving formula. If you know how did you derive formula then you got soul of this problem. After formula it;'s just calculations and coding that formula. Nice work on explanation and code part too. Keep up the good work.
Here, we are searching for the min in the N-1 Floors. Instead we can do a binary search and reduce the complexity from O(N) to O(logN). That would reduce overall complexity from O(EN^2) to O(ENlogN)
6:19 How is x-1 are the floors remaining after dropping an egg from xth floor? That can be anything less than x right? Shouldn't you have written x-constant? (Since that can be anything from x-1 to 0)
They have a mistake in the blog post: if we have a lot of eggs then the solution is (1 + log2 n), not log2 n. I.e you have 2 floors and 1000 eggs, still need to try both floors. log2 of 2 is 1, the answer is 2.
Thanks for this wonderful explanation Gaurav. I had a doubt @13:23 you mentioned that the complexity of this problem is O(n*e*n) which is O(n^2*e). However, if we consider it as table filling problem. we are filling only n*e cells in the table so ideally we are solving n*e sub problems. so isn't it O(n*e) rather than O(n^2*e)? Please explain.
Hello Sir, As you have discussed earlier in this video a method with time complexity O(sqrt(N)) then why we doind Dynamic programming solution even it has bad time colmplexity?
How should I learn to break problems with maths like this ? Btw this is my last year at high school if ever u wanna know my math level. Are there any books u could recommend to study maths in algorithmic problem solving ?
Hey Gaurav, a very stupid question; The original problem was to find the threshold floor. What we have found out is the minimum number of tries that are required to find the threshold floor. Thoughts?
+Gaurav bhola, haha not exactly. The original problem was to find the minimum number of tries to get to the threshold floor. I tried to go step by step to make the question clearer, so I might have mentioned the problem statement incorrectly :-p
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).
With Brute Force, the time complexity is O(N). And with DP, time complexity is O(N*e*log(N)). Which is higher than the brute force one. I m confused here. I understood the DP part and mathematic equation though.
Hey, i am trying much to be a great programmer but I can't think the solution of the problem immediately I take 1 2 days whole to get to the solution can you please guide how can I improve my speed to solve much problems.
how to apply mathematics to solve these problems. how did you come up with a thought to use differentiation to solve maxima,minima. i studied differentiation but application is zero.. could you please share some good video which can fill up this gap
The DP solution gives the minimal number of tries. Now suppose we have n=100000 and e=500, I need to find out the threshold floor where egg breaks. And for every floor i want to check, user gives me input that egg is broken or not. Will binary search work for this case?
Practically "0" floors will never come up, but when we put x = 1 in the formula, then F[0, e-1] comes up. For this case, I was asking about the base condition.
why do we have to check for maximum required eggs from x = 0 to n -1 cant we just check for only n - 1 as it will require more tries when compared to all floors below it
bhaiya please make a video on binary search.There are some ques which dont look like they can be solved by b.search but in actual b.search is the soln.pls go deep in its concepts
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.
how the dp is better than sqrt decomposition approach...dp is running in O(n^3) but sqrt decomposition is running in O(sqrt(n)) can you please explain?
Hi Gaurav, Thanks for nice explanation. I have one query, My solution is coming 4 tries for 7 floors and 2 eggs but yours is 3 tries .. could you please explain how it could be 3 ?
Binary search wouldn't be feasible for this problem. If you have less than log(N) eggs, narrowing down to the threshold floor is not always possible.
Eg: 100 floors and 2 eggs.
Throw the egg on floor 50. Breaks.
Throw the egg on floor 25. Breaks.
Uh oh...
Also, thanks to Banipreet Singh Raheja for pointing out two further optimised solutions here: leetcode.com/problems/super-egg-drop/solution/
Cheers!
I am late but using binary search with another hypothesis(i.e finding no of floors with d attempts and n eggs) can optimize the solution..just type in egg dropping problem Brilliant on google and search for the resource on brilliant website, hope it helps :)
Do linear search for last egg in the remaining range?
using binomial coefficient and binary search method we can solve it in O(nlog(k)) time.
www.geeksforgeeks.org/eggs-dropping-puzzle-binomial-coefficient-and-binary-search-solution/
If possible please explain this.
Varun Jain
We can use binary search also, no problem with that :)
Your explanation is very nice. Totally admire your effort :)
But, I am concerned about, How did we get this equation ?
And i always thought where will i use differentiation after my schools, now i have an ans 😂🤣
Hahaha, me too 😛
Now I wonder where would I drop E eggs from N floors xD Just kidding. Great explanation man!
Thanks for explaining each step with such clarity. I love the way you progress toward the problem as to why and how you are doing what you are doing. Don't trade this part for speed-or-anything. Some other channels really lack this as they are just vomiting out things they have mugged up, not telling why and what of the approach. Keep making such videos. Subscribed for eternity.
Thanks Muskan!
for most tutorials on the TH-cam I have to watch on 2x speed. For your videos I have to watch on 0.75x.
Awesome video, thank you.
Watching this video after 7 years 😅
Still seems one of the perfect explanations - Finding the 2(root(n)) approach was OP🔥
Uff what a legend. Raungte khade kar dene wali explanation!
You are great man !! Simply great !! Not just spitting out some mugged up or already cooked up stuff., but explaining everything to the core that too in a simple and effective way. Great job. Keep up the good job and enlighten more people like me.
Thanks Gokul!
For some eggs "e", Minimum number of trials required for "n"th floor would be "t"
such that tCe >=n and (t-1)Ce
+gagan nagpal What is C?
Gaurav Sen binomial coefficient
Sorry Gagan, I didn't understand why that would would work. :-/
Could you explain in some detail, or by taking an example?
Hi, I got this solution from here brilliant.org/wiki/egg-dropping/ (last para)
But a very formal proof is given, then I came up with my own greedy proof and here it is.
So, Idea is to maximize the number of floors that we can cover given "t" trials and "e" eggs.
Take some examples for clarity:
t=3,e=1 answer is 3 (1+1+1)
t=5,e=2 answer is 15(5+4+3+2+1)
t=14,e=2 answer is 105(15+14+13......2+1)
{
These answers are inspired by 2 egg puzzle, i.e. given two eggs and "n" floor,find minimum trials
eg
For n=100 , e=2 answer is 14
as the first trial is at 14 then at 27(14+13) then at 39(14+13+12) and so....
}
Here, intuitively we are choosing our first trial as t , such that if egg breaks here then (t-1) must be covered by remaining eggs and further our next trial is at t+t-1 because we have wasted 1 trial at "t" floor, so we can go maximum t-1 more floors ahead and so on...
So every time when eggs are 2, the answer is always the minimum value of" x" such that x+(x-1)+(x-2)+...+1 >=n.
Also, we can say that for "t" trials, and eggs =2, we can go for (t+1)C2 floors ahead eg t=14, floors=105.
So far so good.
Now, things get tricky for eggs=3,4,5
Let us try to think in the same direction for eggs=3,
Here, we should drop our first egg at a floor "f" such that (f-1) can easily be covered by 2 eggs, then are second drop should be at f+(f-1) floor, using the same analogy.
and we already know that the maximum number of floors with 2 eggs and "t" trials are given by (t+1)C2.
So, in effect for eggs =3, and "x" trials, we can cover 2C2 + 3C2 + 4C2+...+(x-1)C2 + xC2 = (x+1)C3 floors.
Hence , we can follow up the pattern and hence the answer.
I hope you may get the essence of it, idea is to maximize the floors by eggs.
quite possibly , the best explanation of this problem from algorithmic point of view.
Great!
Gaurav sen and pepcoding made this question crystal clear for me
@@creativegiant148 pepcoding or Aditya verma
You can make improvement in the innermost loop by doing Binary Search instead of linear search which would make Time Complexity of your code to O(n*e*log(n)).
Yeah that's a good catch.
Thanks brother.Your way of analysis such difficult problems is awesome in a very young age.Praying for your bright future .God bless you..
Amazing! With the clarity of concept as well as the underlying mathematics, no wonder you work for directi!(saw that from comments) Seeing your approach of problem solving I was thinking if "this guy is from IIT?" and "that's the way true engineer solves problem!". You have definitely motivated me to go more for problem solving! Please upload more videos whenever you get the time. It would be great to get insights from your approach to problem solving :)
Thanks Shivank! I am glad it helped :-D
Gave me the intuition I was looking for.
Thank you!
Please keep up the good work.🙌
Hey Gaurav, I really like the videos you make. Also, I just wanted to say that whenever you are speaking something I feel like you're going to burst into laughter. 😂 That really makes your videos kinda different in a positive way. :))
Thanks Bhargav!
I saw a few more on youtube but your is best explanation!Thank you.
Thanks!
At 16:45 , n=2 and e=2
so
f[2][2] = max(f[2-1][2],f[1-1][2-1]) , here x =1
f[2][2] = max(f[1][2],f[0][1]) , instead of max(f[1][2],f[1][1])
but now the answer will not be 2 so we have to iterate x to n which will include the case when we drop the egg from the top most floor as well.
P.S: Please let me know I am getting something wrong here. :D
No need to solve, the egg will break from 1st floor itself ! :D
Hahaha
Watching this at 3 AM. Loving it ❤️
Gr8 Explanation!! Noticed n=7 and e=2 has to have 4 instead of 3. I also created PR on your code.
In the array at the end of the video, I think that F[7][2] should be 4. If you run your code with N=8 and K=2, F[7][2] is 4.
Thanks so much Martin! I updated the code now :D
Egg broke and hence he changed his t-shirt 13:53
Hahaha 😛
You are a wonderful wonderful teacher bhaiya ✅✅
Thanks!
Very neat explanation
I also had the same idea of using binary search. Suppose floors are numbered from 1..10, we drop a egg to floor 5. If it breaks, then we must search from 1..5, else from 6..10. This will be at max O(log2(n))
I read about 100 floors, 2 eggs. Now it is clear why binary search wont work. We only have 2 eggs, if they both break we cannot get the answer. eg for 100 floors, if threshold of egg is 13, we will break egg at floor 50, then at floor 25. We wont have any remaining eggs to test.
Thats right :-)
My mind was now accepting if egg will be ever safe as if we drop even from a foot high :-) The more realistic object should have been coconut, pumpkin etc ... :-)
Anyway idea was good, good explanation.
Thank you 😁
The moment u started differentiation it strumbled me
Hi Gaurav, excellent explanation. My question is: what is the relationship between the first part of the explanation where you showed that the minimum number of tries is 2 times square-root of N and the later part where you proved the generic case with the minimization?
Oh, I guess the 'brute-force' tries we do within B floors makes it not the best solution... let me know if that is it.
Heard a lot about DP but never knew its this much fun.....I Just learnt my first DP solved problem!!!
Thanks a lot...
Thanks for the clear explanation, @16:18, as x = 1, then F[x-1][e-1] becomes F[0][1], any reason for saying it as F[1][1]
Hi Gaurav, while reaching the end of your video, can you please explain why you took the value of x-1 as 1 in your second function which was F(x-1)(e-1) while you started with x=1.
Thanks in advance
I have the same question
Your first analytic solution of Y = (B + N/B) is based on a fixed size of floors within each segment of floors.
By minimizing Y you get that B=SQRT(N)
For example for N=100, B=10 which tell us that the best attempts are at the lower segment and the top segment suffers from 20 attempts.
A better solution will be if we choose, instead, a decreasing size for each segment of floors;
For the first trial you go [B] floors but for the next you go only [B-1] and the next will be [B-2], ..., [B-B]
By having decreasing sizes, the maximum trials for each segment is now fixed [B], [B-1+1], [B-2+2] ... [B].
The sum of these variable size segment is [B+0] + [B-1]+[B-2]....+[B-B] = 0.5*B^2 = N and therefore;
The optimal initial size B=SQRT(2)*SQRT(N)
For example if N=100 --> B=14
+Rbi Pro Thats correct, and that is what the solution uses for egg size 2.
In fact, recursively, we are looking at segments which can be completed using 1 egg less and one turn less everytime we have to make a throw. Maybe a direct formula can be found for f(n,e), but I don't know it :-p
You have an amazing explanation skills.
at 16:28 Time, you say F[1] when x =1 , but in the formula it is F[x-1] so should not it be F[0] ??
@Gaurav , your second F[x-1][e-1] says to consider x-1 floors for e-1 eggs. But in your example f[2][2] this will amount to F[0][1] which I didn't understand why you missed ? Can you clarify this .
your way of explaination is amazing..keep it up bro!!
Thanks Anup! 🙂
now I know how to break egg with DP -;). thank you. Clearly explained
When I started learning programming , I loved Java a lot, but there was no one in my college to guide me. Even I remember geeksforgeeks don't use to have its maximum codes in java those days. So, even wanting to do those things, I couldn't do them. Even if I wanted to do them in Java myself I was not sure about if my solution is correct or not. Now coders like you guys make life of people like us great. You guys are really trying your best to promote the coding culture among college graduates. Hope to contribute like you guys one day.
Good work Gaurav, keep sharing the knowledge. At least I don't have to bother to learn DS Algo now. It might be little late than usual for learning them but definitely its not over.
That's the purpose of the channel :)
Let's do this!
@@gkcs Sure man
making omelette of it will be good choice in our floor rather than throwing and breaking it.
For those wondering, the min. number of tries taken in the last example (when n=8) is 4 ( th-cam.com/video/o_AJ3VWQMzA/w-d-xo.html ), while in the 2nd (minimization using derivative) case, it would be = 2*sqrt(8) = 2 * sqrt(4 * 2) = 2 * 2 * sqrt(2) = 4 * 1.41, which is greater than 4. #IDoNotKnowWhyIPostedThis?
Thanks for posting this 😁
#ThanksForPostingThis
Bro I don't understand why (N/B)+B and why we use differentiation. Can you please explain in short? Thanks for your awesome teaching... :)
It seems to be human eggs otherwise egg would have be broken from 1st floor
First of all ,Thank you for sharing knowledge. I have a doubt. Why are we not throwing egg from the last floor , for example if n=5 from 5th floor? Please correct me if i have misunderstood something.
Understood the problem... But can't understand why he changed the shirt 5 time in the video.... 😂😂😂
I was wondering the same
Outstanding Sir
Thank you!
@@gkcs You made it so easy to understand.
@@gkcs You made it so easy to understand.
Great explanation! However I am doubtful about the solution B = root(N) (at time 5:41 in the video). I think it was for the case of 2 eggs. For two eggs and 100 floors problem it would give number of tries as 20 but the answer is 14.
It is a solution, but not an optimal one.
Better than brute force though :)
Another solutions, try from 1st, then 2nd floor, then 4th floor, then 8th foor, then 16th floor so on. Basically 2 power n growth every time, Then when it breaks use binary search between that number and last number that doesn't break it
That won't be optimal though. The number of tries could be as large as log(n) + log(n/2) + log(n/4)
= log(n) + log(n) - 1 + log(n) - 2 + log(n) - 3 + ... + 1
= log(n)^2 / 2
Try the approach for 100 floors. It's more than 14 tries.
Hello@@gkcs thanks for replying. Lets assume that our floors are a power 2. So lets assumed this apartment has 128 floors. So now if I jump starting from 0 all the way till 128 in powers of 2. I will be attempting from these floors = [1 2 4 8 16 32 64 128]
So if worst case scenario I realize that my egg breaks for the first time on the top floor only. That means the egg breaks somewhere between 64-128 floors. That means If I do Binary search between these numbers my worst case scenario Big O will be log(2^(n-1)) where n is 7 here (2^7 = 128). This is worst case complexity. Avg case will be less than this right. So are you saying its bad because log of a exponential number is being done here? If that's the case maybe we can use this approach and then divide this part with your block approach. My intent is if n is large like a million, I will find the range quicker with exponential jumps. Please tell if I am wrong somewhere?
@@prabhatracherla3098 take your time and think it through. Can you binary search after breaking an egg at 128?
No. What if you break the second egg at midpoint? You have no more eggs to search with.
If you do a linear search after it breaks at 128, you have reduced the size to 64-128. That's N/2 tries worst case. Pretty bad.
The approaches here are O(sqrt(n)) and better.
Googling differentiation formulas in between 😁
Amazing now everything is clear to me.Thanks
Thanks for the video! I really enjoy the way you explain things. It is very nice to see the dynamic programming approach to the egg dropping problem. I think though that your logic has a mistake. I implement your algorithm and it gives wrong results. For example it produces F[10,2]=4 instead of 5. In fact, the path predicted if the first two attempts do not break the egg is floors 3 and 6 (which is the correct answer by the way), but then we are left with two eggs and 4 floors to check (7, 8, 9 and 10), which requires a minimum of 3 attempts, so 5 in total. I think that I have pinpointed the mistake at your logic. This problem is kindof special over other dynamic programming problems in the sense that we cannot perform the operations in any order we like. The first steps can be done only in increasing order of floors. When you split the building to bottom and top parts, you ignore this fact and you just add 1 attempt for floor x. This is true for the bottom part of the building, as you are going to treat all its floors in the recursion. For the top part of the building though, this is not true. Your assumption that you reached x with a single attempt is not correct, so for this case you have to add an extra number of attempts, which have been already performed at the bottom part, to reach x. I think this number is int((x-1)/((2**e)-1) but I might be wrong. Thanks again for the video.
Hey Nikolaos, could you try to run the code in the link in the description? I don't think it has a mistake :)
@@gkcs I tried the code. It's what I have understood from the video, and it has the bug I mentioned. For F[10][2] it gives 4. To convince yourself that it is wrong just take the F[100][2]=14 result. There is no way to check 100 floors with 14 tries, by just using 2 eggs. I think what you need to do to fix it is to change your line 23 to:
final int EggSurvivedResult = results[i - x][j] + (x-1)/((int)Math.pow(2, j)-1);
I'll check this out, thanks!
@@gkcs OK... I'm wrong :( Sorry for that. It was my misinterpretation of the DP algorithm results when I was trying to derive the non-DP solution. I lead myself to a different solution, which is not the optimal one, so I modified your algorithm to reach to it. Now I understand better the results of your algorithm, which are correct. At least with two eggs, the problem F[10][2] is indeed 4, and it means start dropping the egg from the 4th floor (not the 3rd as I mentioned earlier) and then move to the 7th (decrease the step by 1). This leads to worst case scenario of 4. The same is true for the F[100][2], which is 14 with the same logic (start dropping at 14th, then 27th, etc, ending up with up to 14 attempts). I will now try to understand the results for eggs>2.
Great! Just relieved I don't have to dig in the code again 😁
great explanation, thanks.
What if it breaks in my hand by taking upstairs do we consider boundary cases too :D, jokes apart your videos and understanding
are awesome.
shouldn't the worst number of tries be (N/B) + B - 1? That makes it equal to (2 * sqrt(N)) - 1 worst tries. Doesn't affect the differentiation though. Good video, Thanks!
fastest case answer throw from the first floor (if i am the owner of first floor) possibility if it breaks then threshold floor is first floor, if it doesnt break then definitely threshold floor is the second floor because second floor owner will definitely break it by throwing it into someones head
In case dynamic programming seems too difficult, we can try practically by taking some eggs in a large building....
Hahaha!
I know it's quite late but I must comment. Got to keep the patience to understand this but really nice work done here. especially deriving formula. If you know how did you derive formula then you got soul of this problem. After formula it;'s just calculations and coding that formula. Nice work on explanation and code part too. Keep up the good work.
May be this video also help to relate to Gaurav's formula : th-cam.com/video/KVfxgpI3Tv0/w-d-xo.html
Thanks!
Here, we are searching for the min in the N-1 Floors. Instead we can do a binary search and reduce the complexity from O(N) to O(logN). That would reduce overall complexity from O(EN^2) to O(ENlogN)
Are you sure?
Give it a try 😛
@@gkcs I Just did. Infact O(EN^2) gives a Time limit exceeded on Leetcode for 100 Eggs and 8191 floors
We can always use binary serach and use the last egg for linear serach.
This would not be optimal. Try it with 2 eggs and 100 floors. Our solution is 14 worst case tries. Binary search is 50 worst case tries.
6:19 How is x-1 are the floors remaining after dropping an egg from xth floor? That can be anything less than x right? Shouldn't you have written x-constant? (Since that can be anything from x-1 to 0)
You break at most one egg with one throw.
They have a mistake in the blog post: if we have a lot of eggs then the solution is (1 + log2 n), not log2 n. I.e you have 2 floors and 1000 eggs, still need to try both floors. log2 of 2 is 1, the answer is 2.
Good catch. The asymptotic complexity is O(log(N)).
Love this - very clear
Thanks for this wonderful explanation Gaurav. I had a doubt @13:23 you mentioned that the complexity of this problem is O(n*e*n) which is O(n^2*e). However, if we consider it as table filling problem. we are filling only n*e cells in the table so ideally we are solving n*e sub problems. so isn't it O(n*e) rather than O(n^2*e)? Please explain.
You need to find the max in each cell. That takes O(n) time. Hence n^2*e in total.
runtime for (i), (j) and (i,j) things i believe
Thank you so much for this awesome explanation!
very nice explanation. Please do more!!
Thanks Janani!
superb gaurav bhai
+Tolani Mahesh Thanks!
I have a question...
Why did you differentiate ? why w.r.t. B ?
because B is varying, N is fixed
@@anshulkoshyari1356 I know that, but why deferentiating that ?
Hello Sir,
As you have discussed earlier in this video a method with time complexity O(sqrt(N)) then why we doind Dynamic programming solution even it has bad time colmplexity?
Because the DP solution is correct and the other isn't. We want optimal number of tries, which sqrt decomposition sort of gives us.
@@gkcs "which sqrt decomposition sort of gives us." What does it mean?. Please elaborate on the reason for choosing the DP approach.
How should I learn to break problems with maths like this ? Btw this is my last year at high school if ever u wanna know my math level. Are there any books u could recommend to study maths in algorithmic problem solving ?
Try these blogs: www.ardendertat.com/2012/01/09/programming-interview-questions/
@@gkcs ohh thanks a lot !
hi gaurav sen, i have a doubt, why are you minimizing the maximum worst cases from 1 to n-1? and not 1 to n? kindly explain pls.
can you please explain why we have to take maximum of F(x-1,e-1),F(n-x,e)
Hey Gaurav, a very stupid question;
The original problem was to find the threshold floor. What we have found out is the minimum number of tries that are required to find the threshold floor. Thoughts?
+Gaurav bhola, haha not exactly. The original problem was to find the minimum number of tries to get to the threshold floor. I tried to go step by step to make the question clearer, so I might have mentioned the problem statement incorrectly :-p
Never looked at eggs this way...
This really helped me a lot! Thanks :)
Simple AP GP inequality will work too . remind me of my FIITJEE days.😂
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).
Very clear explanation. Thank you
Thanks Lokesh!
your explanation is awesome but i have doubt x will be up to n -1 not including n.
Binary search till we have single egg remaining.
Ans would be no. of eggs -1 + remaining range to be searched.
Any thoughts?
The worst case is still pretty bad. If n is much larger than e, we have to search on n/2^e.
@@gkcs what if we apply incremental steps? Start from 0, then 2 then 4 the 16 ...
12:52 should'nt the x should start from 1? It would result in a loop, otherwise!
With Brute Force, the time complexity is O(N). And with DP, time complexity is O(N*e*log(N)). Which is higher than the brute force one. I m confused here. I understood the DP part and mathematic equation though.
You're mixing the number of tries in brute force with the time complexity of finding minimum tries in the DP approach.
Hey, i am trying much to be a great programmer but I can't think the solution of the problem immediately I take 1 2 days whole to get to the solution can you please guide how can I improve my speed to solve much problems.
how to apply mathematics to solve these problems. how did you come up with a thought to use differentiation to solve maxima,minima. i studied differentiation but application is zero.. could you please share some good video which can fill up this gap
Love you,bro. Best explanation ever
Thanks!
The DP solution gives the minimal number of tries. Now suppose we have n=100000 and e=500, I need to find out the threshold floor where egg breaks. And for every floor i want to check, user gives me input that egg is broken or not.
Will binary search work for this case?
Yes. Eggs > log(N).
Why did you rejected (2*N^1/2) algo? Is it because it doesn't have the consideration of e(no of eggs)?
I rejected it because the next one gave the optimal answer.
@@gkcsWhy? root of n is less than n^2*e?
@@gkcs ....??
In the process of calculating the values like F[2][2], we'll find max(F[1][2], F[0][1]), won't there be a base condition where F[0][e] = 0?
How will "0" floors come up?
Practically "0" floors will never come up, but when we put x = 1 in the formula, then F[0, e-1] comes up. For this case, I was asking about the base condition.
Awesome explanation.
Thanks Bala!
There is a problem similar to this in codechef,thanks buddy
which approach is better for beginner in dynamic programing either top-down or bottom-up?
Well explained except for the "max" part. Do you have a better explanation for that? Thanks a lot for posting this video :)
hi can anyone please tell what would be the output when floors>1 and egss=0 if reach this case in recursion ?
This code may have a large time complexity for large values of eggs and floors. Is there any optimised approach to this problem ?
There is an approach which uses binary search to find an optimal floor. I think the time complexity reduces to n*logE there.
@@gkcs Thank you....
why do we have to check for maximum required eggs from x = 0 to n -1 cant we just check for only n - 1 as it will require more tries when compared to all floors below it
Think how we derived the formula and what x means again.
bhaiya please make a video on binary search.There are some ques which dont look like they can be solved by b.search but in actual b.search is the soln.pls go deep in its concepts
I have in many videos. You can check out the editorials I have made. Many have binary search in them
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.
Every throw of the egg is counted as an attempt. We need to minimize the number of throws.
Can you provide any free resources to learn aptitude ?
Why don't I get this? Am I missing any prerequisite? Anyway, keep up the good work!
Dynamic Programming is a prerequisite for this video 🙂
That's very helpful!!
Thanks!
how the dp is better than sqrt decomposition approach...dp is running in O(n^3) but sqrt decomposition is running in O(sqrt(n))
can you please explain?
Hi Gaurav, Thanks for nice explanation.
I have one query, My solution is coming 4 tries for 7 floors and 2 eggs but yours is 3 tries .. could you please explain how it could be 3 ?
this should not 3
this should be 4
It's true. For 7 floors, it should be 4 not 3