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.
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)).
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
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.
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 :)
For those wondering, the min. number of tries taken in the last example (when n=8) is 4 ( ua-cam.com/video/o_AJ3VWQMzA/v-deo.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?
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)
@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 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
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.
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
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?
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.
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.
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. :))
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
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.
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.
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)
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.
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?
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.
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?
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.
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.
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.
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
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.
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?
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
can we use a binary search with logN comparison instead of sqrt decomposition for finding the solution??(I am not sure with binary search correctness for this)
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).
i) N was the number of tries in worst case using Brute Force Approach. ii) 2 * root(N) was the number of tries in the worst case using SquareRoot Decomposition. iii) O(N^2*e) is Worst Case Time Complexity to solve the problem and the number of TRIES here will be the minimum possible.
when we do a sqrt decomposition, so if we have 1 egg and that breaks at say B then how can we calculate the real answer as we dont have any more egss. So for sqrt is it the condition that the egg should be atleast 2?
Yes, you need atleast two eggs to break the tower into blocks. In fact, sqrt decomposition is not optimal for the given problem. Consider a tower of 100 floors. Each block of size sqrt(100) = 10 floors. That means, in the worst case, we need B + N/B tries. Thats 10+10=20. On the other hand, the recursive approach needs only 13 tries.
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.
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!
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 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 ?
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!
for most tutorials on the UA-cam I have to watch on 2x speed. For your videos I have to watch on 0.75x.
Awesome video, thank you.
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 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.
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 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.
Gaurav sen and pepcoding made this question crystal clear for me
@@creativegiant148 pepcoding or Aditya verma
quite possibly , the best explanation of this problem from algorithmic point of view.
Great!
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
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!
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
For those wondering, the min. number of tries taken in the last example (when n=8) is 4 ( ua-cam.com/video/o_AJ3VWQMzA/v-deo.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
Gave me the intuition I was looking for.
Thank you!
Please keep up the good work.🙌
I saw a few more on youtube but your is best explanation!Thank you.
Thanks!
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
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.
@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 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
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 :-)
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
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.
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] ??
No need to solve, the egg will break from 1st floor itself ! :D
Hahaha
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.
Heard a lot about DP but never knew its this much fun.....I Just learnt my first DP solved problem!!!
Thanks a lot...
your way of explaination is amazing..keep it up bro!!
Thanks Anup! 🙂
The moment u started differentiation it strumbled me
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
now I know how to break egg with DP -;). thank you. Clearly explained
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!
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]
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
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 😁
Gr8 Explanation!! Noticed n=7 and e=2 has to have 4 instead of 3. I also created PR on your code.
Watching this at 3 AM. Loving it ❤️
You have an amazing explanation skills.
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 😁
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
You are a wonderful wonderful teacher bhaiya ✅✅
Thanks!
Egg broke and hence he changed his t-shirt 13:53
Hahaha 😛
12:52 should'nt the x should start from 1? It would result in a loop, otherwise!
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... :)
Very neat explanation
can you please explain why we have to take maximum of F(x-1,e-1),F(n-x,e)
This exact question was asked to me in the OpenText final managerial round.
Amazing now everything is clear to me.Thanks
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)).
In case dynamic programming seems too difficult, we can try practically by taking some eggs in a large building....
Hahaha!
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 ?
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.
which approach is better for beginner in dynamic programing either top-down or bottom-up?
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.
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).
Googling differentiation formulas in between 😁
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.
hi can anyone please tell what would be the output when floors>1 and egss=0 if reach this case in recursion ?
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 : ua-cam.com/video/KVfxgpI3Tv0/v-deo.html
Thanks!
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
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
Can't we use binary search like approach?
It's in the pinned comment.
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 :)
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?
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.
can we use a binary search with logN comparison instead of sqrt decomposition for finding the solution??(I am not sure with binary search correctness for this)
Binary search would be a good try. I have added a comment to the video explaining why it wouldn't be optimal, though.
I think when no of floor is fixed than we can use binary search but when it is not fixed than we need to use sqrt decomposition
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.
making omelette of it will be good choice in our floor rather than throwing and breaking it.
Isn't the sqrt(n) computation method better? Why use DP?
very nice explanation. Please do more!!
Thanks Janani!
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....
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).
Wouldn't the columns for e > 2 will always be same? In this case we can reduce the time complexity to O (n * n * 2)
No, they won't.
great explanation, thanks.
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.
Thank you so much for this awesome explanation!
Could you do a binary search version of this problem? This DP is TLE at OJ. Thank you!
Read the pinned comment
hi now u need to get premium to access the solution 😢@@gkcs
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.
Outstanding Sir
Thank you!
@@gkcs You made it so easy to understand.
@@gkcs You made it so easy to understand.
can we do the block skipping with dynamic programming? im confused. N -> root(N) -> O(N square)?
i) N was the number of tries in worst case using Brute Force Approach.
ii) 2 * root(N) was the number of tries in the worst case using SquareRoot Decomposition.
iii) O(N^2*e) is Worst Case Time Complexity to solve the problem and the number of TRIES here will be the minimum possible.
when we do a sqrt decomposition, so if we have 1 egg and that breaks at say B then how can we calculate the real answer as we dont have any more egss.
So for sqrt is it the condition that the egg should be atleast 2?
Yes, you need atleast two eggs to break the tower into blocks. In fact, sqrt decomposition is not optimal for the given problem.
Consider a tower of 100 floors.
Each block of size sqrt(100) = 10 floors.
That means, in the worst case, we need B + N/B tries. Thats 10+10=20.
On the other hand, the recursive approach needs only 13 tries.
As he said in the video,
f(n,1)=n , so u should start dropping eggs right from the first floor itself,
which will be optimal.
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 ....??
Simple AP GP inequality will work too . remind me of my FIITJEE days.😂
Very clear explanation. Thank you
Thanks Lokesh!
Binary search could be used here?
Nope. Not as efficient
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.
It seems to be human eggs otherwise egg would have be broken from 1st floor
Can you provide any free resources to learn aptitude ?
superb gaurav bhai
+Tolani Mahesh Thanks!
Never looked at eggs this way...
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!
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.
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 !
Also what happens if we apply square-root reduction repeatedly? Will it converge to the same results as you established later?
No.
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 ...
What was your initial thinking behind the formula?
may be this : ua-cam.com/video/KVfxgpI3Tv0/v-deo.html
I did not understand why we used diffrentiation to get the square root. Can u plz explain
It's explained in the video. We want minimise the number of tries.
Why don't divide the buildings into halfs and solve it by recursion ? I'll have log n complexity i guess ?
Binary search. Check the description.
Understood the problem... But can't understand why he changed the shirt 5 time in the video.... 😂😂😂
I was wondering the same