(35 votes, average: 3.77 out of 5)There is a building of 100 floors If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.
Check your answer:-
Click here to See AnswerFirst thought which comes to our mind is to use binary search, we first drop Egg#1 from 50th floor, if it does not break, then try the middle of second half, if breaks then we have to try each floor in first half. But this will give worst case number of drops as 50(if it brakes on 50th floor, then we have to try from 1 to 49 floors sequentially).
Second thought is to try xth floor then 2xth floor till 100th, in this case worst case time will be (100/x)+(x-1). worst case will be when Egg #1 breaks at 100th floor then we have to try Egg #2 from (100-x)th to 99th floors. In (100/x) + (x-1) equation, with increase in x, 100/x decreases while (x-1) increases, thus we can minimize it when 100/x = (x-1), this gives x ~10, which gives worst case number as 19 drops.
But increasing the floor every time by x is not a very nice idea, as with each new increase in Egg #1 drop, we should decrease Egg #2 drops to minimize worst case number. so if we drop Egg #1 from xth floor initially, then in next turn we should try x + (x-1)th floor(to keep the worst case number same).
Thus we can say X + (x-1) + (x-2)…1 = 100
X(X+1)/2 = 100 => X=14.
So we should drop Egg #1 from 14th, then 27th, then 39th and so on.
1st. Drop egg from the 50st. floor. Two results break or not . If the egg breaks the nth floor is between 49 and 2, if not we know the nth floor is between 51 and 99 (we know the egg will not break if dropped from the first floor because it is the minimum distance you can drop the egg and we know that the egg will break at floor 100- the maximum distance you can drop the egg). attempt #2 (assume the egg broke when dropped from the 50th floor) drop the egg from the 3rd. floor- one of two can happen, if the egg breaks the nth floor is #3, if not retrieve the egg and drop it from the 26th. floor (half the number of floors between 4 and 50, one of two can happen, if the egg breaks then the nth floor is between 26 and 4 if it does not break the nth floor is between 27 and 50. repeat the process of halving the floors until you get to two floors, the upper floor is the nth floor. It will take you 10 operations to narrow it down to one floor and you will break a total of 5 eggs.
Excellent Approach. Upper limit will keep doing half and lower limit will be incremented by 1. Check the total count that would be less than 51. And it would be half of the 51 + and then half of this further result. (Around 39 and this is the worst case).
This is not exactly the binary search (Divide and Conquer Approach based) but One sided Divide and Conquer and one sided Linear Search based fundamental. Hence rather than taking log(n) time its taking n/2 + log(n) I guess.
how is the time of the second case 100/x + x-1 ?
I try with the 50th… It breaks, 1 st try..
I then try with 25th… It breaks… 2 nd try..
I try with 13… It breaks… 3 rd try..
I try with… 7… it breaks… 4 th try
I try with 4.. It breaks… 5 th try..
I try with 2… It breaks… 6 try..
I try from 1st floor…it should not break.. 7th try..
SO minimum tries required is 7..
Buddy you have 2 eggs not 7
i’m not understanding this..we are given only 2 eggs ..and how did we get the equations
I think we should start from 50the floor.If the first egg breaks ,we have to check lower 50 floors, otherwise upper 50 floors. In either case we have to do the job from downward to upwards.
Its a binary search algorithm.. We can follow both the way 🙂
this is the equivalence partitioning concept also
14 is not correct… because.. 14*7 = 98. .. the first egg breaks at 98th floor… so already 7 tries are over( 1 broken egg.. ).. so now we have to identify in btw 84 and 98… so starting from 85 to 97 = 13 tries.. so total of (7 tries for first egg and 13 tries for second egg = 20 triees minimum..)..
i guess the correct or the minimal ans is 19.. which we can get by giving 10 floors gap… if it breaks at 100th floor.. total 10 tries then 9 tries from 91 to 99 = 19 tries is the optimal solution…..
lol..if egg breaks at 84 , then why to check upto 98 ?
we have to check from 83 to 78 in descesding order and this will add upto only 14 tries !!
The interval between two trials will be like 14,13,12,11,… if u calculate this way, u ll get the answer as 14.
eggs are in boiled condition so no egg will break up to nth floor means 100th floor also
and above 100 their is no up floors
nth floor is the very first floor. Be it a first floor or above egg will break from any height you drop.
assume their is no basement and the building starts from the first floor. then there wont be any floor under that to try if egg breaks from there. so, we dont have to use the egg to experiment. i save both the eggs
The problem is it has 2 eggs suppose you starts from floor 14 and it breaks then you try one more time from which floor????
Burj Khalifa … more than 100 floors 🙂
First take me to the building with 100 floors then I will explain u there