Question: You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?
Answer: The easiest way to do this would be to start from the first floor and drop the egg. If it doesn’t break, move on to the next floor. If it does break, then we know the maximum floor the egg will survive is 0. If we continue this process, we will easily find out the maximum floors the egg will survive with just one egg. So the maximum number of tries is 100 that is when the egg survives even at the 100th floor.
Can we do better? Of course we can. Let’s start at the second floor. If the egg breaks, then we can use the second egg to go back to the first floor and try again. If it does not break, then we can go ahead and try on the 4th floor (in multiples of 2). If it ever breaks, say at floor x, then we know it survived floor x-2. That leaves us with just floor x-1 to try with the second egg. So what is the maximum number of tries possible? It occurs when the egg survives 98 or 99 floors. It will take 50 tries to reach floor 100 and one more egg to try on the 99th floor so the total is 51 tries. Wow, that is almost half of what we had last time.
Can we do even better? Yes we can (Bob, the builder). What if we try at intervals of 3? Applying the same logic as the previous case, we need a max of 35 tries to find out the information (33 tries to reach 99th floor and 2 more on 97th and 98th floor).
Interval – Maximum tries
1 – 100
2 – 51
3 – 35
4 – 29
5 – 25
6 – 21
7 – 20
8 – 19
9 – 19
10 – 19
11 – 19
12 – 19
13 – 19
14 – 20
15 – 20
16 – 21
So picking any one of the intervals with 19 maximum tries would be fine.
Update: Thanks to RiderOfGiraffes for this solution.
Instead of taking equal intervals, we can increase the number of floors by one less than the previous increment. For example, let’s first try at floor 14. If it breaks, then we need 13 more tries to find the solution. If it doesn’t break, then we should try floor 27 (14 + 13). If it breaks, we need 12 more tries to find the solution. So the initial 2 tries plus the additional 12 tries would still be 14 tries in total. If it doesn’t break, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. Since we only need to cover 100 floors, 14 tries is sufficient to find the solution.
Therefore, 14 is the least number of tries to find out the solution.
If you have any questions, please feel free to send me an email at support@mytechinterviews.com. If you have any interview questions which you feel would benefit others, I would love to hear about it.
Related posts:
If you follow this method, what is the worst case number of tries? It will be much more than the answer given.
41 is my answer…
HOW?
Start from first floor. drop the egg.
if it breaks, ans is 0 else goto 2nd floor. drop the egg.
if it breaks, ans is 1 else goto 4th floor. drop the egg.
If it breaks, answer is 1+1+1 tries for this case..
Likewise, if in the worst case, you keep dropping the egg till 64th floor and then finally to 100th floor and if it doesnt break, then you start from 65th floor and keep going one level up each time till 99th floor.
This case would mean log100, 6tries + 35 tries = 41 tries.
Although the minimum could be 1 in best case but here we should answer worst case IMO.
Does this look fine to you guys?
Cheers
Gaurav
We have only two eggs. We cannot start from more than second floor. If it breaks at second floor, then from first floor we can drop the other egg. If it breaks then answer ground floor else first floor. If it does not break when fallen from second floor, then go to 4th floor and so on.
Errata: I made a mistake in my previous post. In the second case where it breaks at 98, I forgot to count the drop at 98, so the total is not 10, it’s 11. Sorry for any confusion.
Yes, you need to remember that there are only 2 eggs. I think you can do it in better than 14, but the answer depends of course at which floor it breaks. Rather than use general formulas I’ll answer it in a narrative.
If you start on the 13th floor and go up by 13s, then the number of tries to reach 91 is 7, assuming it hasn’t broken yet. Now, since you dropped it at 91 and it didn’t break, you still have 2 eggs. So go to 95. If it breaks, then you have to go one floor at a time, because if you go by 2s, and it breaks at 93, say, you won’t know if it would have broken also at 92 (remember, you only have one egg). Then the maximum from there is 92, 93 and 94. that’s 7 + 1 + 3 = 11.
If it doesn’t break at 95, then go to 98. If it breaks, then you have you know that you only have to go 96 and 97, which is 7 + 1 +2 = 10. If it doesn’t break at 98, then you also get 10 because of 99 and 100.
Now, if it breaks at 91, and thus you have only one egg, you have to start at 78 (13 x 6) where you know it didn’t break, and go by ones again, or: 79, 80 – 90 = 12. So the worst case for that would be 12 + 7 = 19. But if the egg breaks at 78, then it would be 12 + 6 =18. And if it breaks at 65, then it is 12 + 5 = 17. You get the picture for that scenario.
However, if you think the egg is never going to make it above 91 (which, realistically of course it will not), then you should go by a smaller number, say 10s. Then there would only be 9 tries after the first egg breaks. So if the egg broke at 40, then it would 9 + 4 =13.
In summary, I think the problem should specify the maximum floor where the egg doesn’t break and then ask for the minumum number of tries.
Well, all of these answers are wrong — for most of these assumed there is infinite supply eggs. Considering that there are only two eggs, someone had suggested that the answer must be 51 (for checking 2 floors at a time).
I believe the correct answer is 35. Let’s try 3 floors at a time (floor 3, 6, 9, …). Let’s say the first egg breaks at floor N. This means we know that it was okay at floor N-3 and it did break at N. That leaves the floors N-1 and N-2 to be tested. We shall now drop the second egg from floor N-2. If it breaks, the max # of floors from which the egg won’t break is N-3. If it didn’t, then we still have the second egg intact, and we shall try the floor N-1. If it breaks, then the max # of floors is N-2, otherwise N.
Guys if we test it with boiled egg then it never break i think so
14 is the correct answer.
There are already detailed exlanation for it.
Question :You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of FLOORS from which the egg can be dropped without breaking IT. What is the minimum number of tries needed to find out the solution?
Answer : This may sound uber wacky, but could it not be possible that the question is structured to hide the fact that the word IT refers not to the eggs but to the FLOORS. So the answer is 0 tries as you cannot break floors by dropping eggs off them
The thing that most of you guys are forgetting is that “You have only 2 eggs”. If you drop it on the 50th floor, it breaks. Then move on to 25th floor and it breaks. Now you are out of eggs and you don’t have an answer. Once it breaks you can’t use them anymore. With that, the binary search method won’t hold.
7 tries are sufficient i guess.. its same as binary search problem. start with floor 50 if it breaks go to 75 if it again breaks then go to (100+75)/2
if it doesnt break go to the previous sub half.
max time is lg(n)
which is 7.
The **minimum number of tries** as stated in the question, is 2 tries.
Guess a floor at random. Drop an egg from it.
Result 1) If it breaks, go one floor lower and drop the other egg. If your random guess was correct, the egg will not break on this floor and you have your answer.
Result 2) If it doesn’t break, go one floor up and drop the other egg. If you random guess was correct, the egg will not break on this floor, and you have your answer.
The maximum number of tries is seven. This can be done using a binary search. Start in the middle (50). If it breaks, go down to half (25) or go up half (75). Repeat. In general, this is log(n) = log(100) =~ 7.
This problem can be done by recursively dividing by half. Lets say you start at max/2 = 50. If it breaks, go lower by half, else it doesnt break go higher by half. So at 50 it doesnt break, you do 50+(100-50)/2= 75 and try again. Keep doing this until you find the floor. Example:
Start at 50 and the egg doesnt break, move to 75 ( quarter of 100).
50
75
At 75 it breaks — new = 75 – (75-50)/2=63
50
75
63
does not break — new = 63 + (75-63)/2=69
50
75
63
69
it breaks — new = 69 – (69-63)/2=66
50
75
63
69
66
it doesnt break — new = 66+(69-66)/2=68
50
75
63
69
66
68
it breaks — new = 68-(68-66)/2=67
At this point if it breaks then the max number of floors is 68, else is 67 and it took 7 tries. At worst case!
Dont see how RiderOfGiraffes’ solution works if we have only 2 eggs. If we start at floor 14 and if the egg breaks, then we’d need to try at floor 13. And what if the egg actually breaks at 1st floor. With this method, we’d need 14 eggs – violates the question!
the correct ans is 51 itself.
someone gave the ans like 14+13
+12+… so on. but what if it breaks on 14th floor? then with remaining one egg he has to check for 13 floors and at the worst case the second egg can break at 13th floor. and who knows if he had tried it in some other floor below 13 also it can break right?
Here’s a better solution:
Start from the 50th floor, if it breaks, move to the 25th, if it doesnt, to the 75, go on halving, like if it does break at 50, move to 25th, if it breaks again, 12th, this way, the no. of possibilities goes on decreasing, coz the upper/ lower limits change depending upon whether the egg breaks or not
The posited problem and subsequent question seem to assume two separate criteria: in the former, you have two eggs, but the latter clearly indicates “how many tries.” Assuming that you only have two tries, then mathematically the minimum is either one or two.
If we omit the constraint on the number of eggs one has, then we can use a binary search algorithm, and the result is (correct me if I’m wrong here, folks) log2(N) + 1, where N is the number of floors.
As an example:
If you have a 100 story building, you can start by dropping the egg at the 50th floor (and we, of course, assume that these eggs were made from genetically engineered chickens and can withstand otherworldly forces).
If the egg breaks, we can rule out the top 50 floors. We then half the distance to the ground, and drop another egg at floor 25.
If the egg survives at floor 25, then we can derive that the answer is somewhere between 25 and 50. We halve the distance between those two floors (roughly the 37th floor) and continue moving up or down depending on the outcome of each test.
So let’s plug in some values here.
Let’s pretend the egg can survive a 16 story drop.
First, we drop at 50, then at 25, then at 13, then at 19, then 16.
Similarly, if it’s at, say 51, we drop at 50, then 75, then 63, then 57, then 54, then 52, then 51.
Hey Guys,
I think every body here is stressing too much to their mind.The answer is 1.You just need one try.(Actually 0 tries as i know the egg will break ultimately after striking the floor)
Its a 100 floor building and an egg dropped from 100th floor would survive to maximum to 99 floor before hitting the ground.
I’d say that the answer is:
ceil( ln( 100 ) / ln( 2 )).
I am not sure 14 is the solution. You have to consider worst case scneario.
Lets say the egg breaks at 98th floor. You need 7 steps to reach 98th floor. The first egg breaks. Then you need 13 more steps with the second egg to ensure up to 97 the egg does not break.
Total steps = 7 + 13 = 20.
The way I model it is, if you are using step x:
worst case number of attempts = (100/x) + x – 1
Taking differential to find maxima:
(-100/x^2) + 1 = 0;
x^2 = 100
x = 10
Worst case scenario you need 19 steps.
@daya :
This is correct. This we can co-relate to a search algorithm in an sorted array.
The above method is called binary search.
Just make an omelette. Why waste even 1 egg, when u know it will break from 1 floor. Mmmm delicious
Inserting the solution given makes it clear the question is not quite correctly posed. Using the exact phrasing of the question we might say:
14 is the minimum number of tries needed to find out the solution.
We might then conduct the experiment and find:
I needed 6 tries to find out the solution.
It would seem very strange, then, to call 14 the minimum number of tries needed to find the solution.
Those people suggesting 1 try ‘if you get lucky’ are missing the idea here. The maximum egg survival floor is exactly n when an egg survives a drop from floor n, but breaks when dropped from floor n+1. When I read “the minimum number of tries needed to find out the solution” I did take it as the ‘best case’ number of tries to find a ‘particular solution’, in which case the answer is 2. You pick the maximum floor wrt egg survival on your first try, and drop from the floor above on your second. For me, ‘minimum’ connotes a particular solution. In fact we are looking for the minimal maximum number of tries! I would have found it less ambiguous if it had been worded “find the minimal maximum number of tries to find the solution in general.”
I think there are 2 categories of people in this forum-first one who had understood the problem and second one who haven’t understand it ….lets explain it once again
the problem statement is a bit confusing- we don’t have to find the floor number,we had to find the number of tries in which this floor can be found…..lets assume we take n tries i.e. we start at nth floor.If it breaks we had find the solution in one try ,if it doesn’t break we will throw the egg from n+(n-1) floor.Again if it breaks,it means the culprit floor is between nth and 2nth-1 floor so in worst case scenario we would be able to find that floor in (2n-1)-(n-1) = n-2 attempts.
So total attempts are 2 + (n-2)=n attempts which we had already assumed.
We would continue this till we reach the top floor.
So the equation we will get is
n+(n-1)+(n-2)+……+ 2+1 > 100
n(n+1)/2>100
which gives n>13 or n = 14 attempts .
If there would have been 1000 floors then same equation would have been used.
Hope this helps.
What if your egg breaks on the 100th floor and the 50th floor. You won’t have any more eggs to try with. This won’t solve the problem.
1 14 13
2 27 12
3 39 11
4 51 10
5 61 9
6 70 8
7 78 7
8 85 6
9 91 5
10 96 4
11 100
First try at 100th floor it it breaks then try in 100/2=50th floor if it didnt break then try in 75th floor else 25th floor. Continue above steps.
We want a guaranteed answer at the end of the tries. This is not possible with just one try.
Toshiro, what would you do if the first egg doesn’t break on the 50th floor?
couldn’t the minimum number of tries just be 1? you could get lucky and pick the correct floor first… I know this isn’t a mathematical proof, but it is definitely possible that someone figures this out in 1 try.
if you ONLY have 2 eggs then there’s no better solution than 51 tries.
John Leach’s comment is good, but really we don’t have to drop the egg at all. Has NO ONE at Google ever dropped an egg from a counter and had it break? Dropping an egg from multiple stories is ridiculous!
Yes, coming up with mathematical answers is important. Knowing what questions are worth asking is more so.
(Okay, wise guy, so now we’re going to drop an experimental ball and want to know when it breaks. Happy now?)
Yes, but John Leach still applies.
In addition to the valid point about weakening, this is the type of test where (as an interviewer) I would want to hear something like “common knowledge would seem to indicate that an egg will not survive a fall of even one story. eggs break when you jostle the carton, let alone when you drop them 10 or 20 feet. so any testing regime would begin with a sanity check – drop it from the minimum distance to verify that our common-sense assumption of immediate breakage is in fact right.”
u got 2 eggs.. so only 2 chances.. lol
general formula for it is
F(b, d)=F(b-1, d-1)+F(b, d-1)+1
where F(b, d) is number of floors such that if you are given b number of balls, d number of drops and f100
d=14
I really dislike puzzles like this. An egg that survived a drop would be weakened. Information about subsequent drops would be useless without knowledge of how the eggs are affected by previous drops.
Call me a pedant, but if you aren’t supposed to consider this then what else aren’t you supposed to consider?
yeah, i noticed i miss read the 2 eggs part. heh, eggs are always in plenty stock where i’m from
Now what will happen if the egg breaks at floor 50 and then it breaks again at floor 25. You are out of eggs as well as luck. You will not be able to identify which floor is the maximum.
I think 7 tries should be enough.
With n floors we have n+1 possible outcomes. n floors + 0 (the egg always breaks).
We know that if the egg doesn’t break when dropped from floor X the answer will be either equal or larger then X. If the egg breaks the answer will be smaller then X.
Let’s start at the 1/2*n floor and drop the egg.
If it breaks the maximum floor is below 1/2*n, if it doesn’t break the floor is above 1/2*n. Now we simply repeat the drop at 1/2*n + 1/4*n or at 1/4*n. This way we half the solution area with every try.
100 can be divided by two 7 times until we get 1. Or said differently, we’re looking for the smallest y in the following equation: 2 ^ y >= n.
The minimum number would imho be 1 because if you are very lucky it breaks already on the first floor
I guess I would have “failed” on this interview question.
My answer would be Zero. All the extra information seems designed to obfuscate the problem.
Aswin,Sorry for my poor english. i just want to point out that using the initial solution can not always produce the optimal result.I have provided two cases when eggs survive in 2 or 5 floor to explain it
I am sorry didxga, I do not quite understand what you are trying to explain. Could you try explaining it in a little more detail. Thanks.
Yes RiderOfGiraffes, recursively making the intervals half is not going to work. You first is better though.
What if the eggs can survive in 2 storey. using the method with interval of 1 you needs 3 tries,but using the method with interval of 8 needs 4 tries. likewise if the egg can survive in 5 storey.using the method with interval of 3 need 4 tries ,but using the method with interval of 8 you need 7 tries.maybe some other factors should consider, like probability.
Final comment. The asymmetry is more severe in the attempt to recurse than just the egg broken or not. We’ve already used a drop when we go to the top half, so the recursion isn’t straight-forward, and the optimal solution is the one I first gave.
Actually, rather than the “double up till you exceed your desired value” strategy you should use “divide and conquer.”
Let’s drop the egg from the 50th floor. Whether it breaks or not we can use the other egg to cover the half we want, so using at most 1+50 tests.
But the two halves aren’t equal, because if it doesn’t break we can use it again in the top half, dropping it from 75. Perhaps we should start with dropping it from 33, then if it breaks fill the gap, and if it doesn’t, recurse in the top portion.
So what fraction should we go up? Overviously 50% is too much, is there a nice ratio? Can we prove it?
A good guess in these cases is the Golden Section, in this case something like 1/phi or 0.618034. So perhaps we should go up 38 floors, leaving 62 above.
Another good guess would use 1/e, or the 37th floor. That seems to big. In either case, it’s not hard to push through this analysis.
OK, so now you know it can be done in 19 tries, let’s see if it can be done in fewer. Let’s go for 18.
That means I can first drop the egg from the 18th floor and if it breaks, try 1 through 17. If it doesn’t break then I’ve used one attempt and I’m allowed 17 more.
Let’s try the 35th floor. If it breaks then I can try 19 through 34, again a maximum of 18 (2 already plus another 16). If it doesn’t break then I’ve used two attempts and I’m allowed 16 more.
Continuing like this I can get up to 171, and spotting that pattern shows that 171 is 18x(18+1)/1, or the sum of numbers 1 through 18.
OK, so I should be able to get 100 floors with a starting value of 14. 14x(14+1)/2 = 105, and a check check shows I can do that.
So I can do it in 14, which I’m pretty sure is less than your 19. Given that you asked:
What is the minimum number of tries
needed to find that information?