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:
@DPT Binary search won’t work since you only have 2 eggs. What happens once the eggs break in the first two steps, you won’t have any more eggs to try for the remaining 5 steps.
Actually, I get the same solution as the updated solution above. But the actual should be 15, as you always needs one more try (actually breaking the egg) in order to confirm that’s the highest floor you can go. In another words, you can never determine the highest floor with a single try (except floor 100, which we won’t start there).
the first thing that came to mind was binary search!
that makes it 7
Fools! The answer is 2.
You go to a random floor, number x, and drop the first egg. It survives. You go to floor x+1 and it breaks. Floor x is the maximum height. This is the absolute minimum and relies on pure luck.
Plus you only have 2 eggs.
@Alexander:
For a higher number of floors than 2, we can still get a certain answer.
Since we are talking about the minimum number of tries here, we do need to choose the floors we will test from.
Lets say, for an interval of 3 – we try third floor, and the first egg breaks. We try the 1st floor next. If the egg breaks, you know its the zeroth floor. If the egg survives, you try the 2nd floor next. Either ways, you have a definitive answer.
Say for an interval of 4 – First attempt on floor 4, say the first egg breaks. Second attempt on floor 2. If egg breaks, we know the answer is 1. Egg survives, then we get to try floor 3.
First attempt on floor 5, the first egg breaks. Second attempt on floor 2. Egg breaks, we know answer is 1. Egg survives, we get to try 3. We’ll have a definitive answer in this case too.
.. and so on.
binary search gave me 7 as well. Here’s the python code to demonstrate it:
a = range (1,101)
for x in a:
max = 100
y = max
min = 1
count = 0
while (1):
if (x == y):
break
y = (max + min) // 2
if (x > y):
min = y
else:
max = y
print "Launching the egg from floor " + str(y) + " crashed the egg"
count += 1
print str(x) + " took " + str(count) + " launches."
log N or binary search way won’t work.
You guy forgot that there are only 2 eggs. For log N or binary search way to work, you will need (log N) eggs for worst case.
I got the result 7
1 50
2 25
3 13
4 7
5 4
6 2
7 1
This is binary search logic
- Sankar Venkat
I kind of thought the same thing as Cong. It should not take more than Log100 base 2 steps to solve the problem.
Anyone for issues in that?
what if it breaks at 50th floor, you will have to try 25th floor. Let’s say it breaks there as well… you are left with no more eggs and you can’t give an answer. The simple binary division of the floors won’t work with a limited supply of eggs.
I don’t agree with most solutions.
Try 50th floor first. If it doesn’t break, try 75th. If does break, try 25th. Each you are eliminating half the floors. So 100/2^n>1, n=6
First of all an egg will break if you dropped it from the stove…Question Stupid!!!!
assuming stress fractures from multiple egg drops doesnt scew the results
Alexander, your 2 assumptions are wrong (and the solution is therefore sub-optimal)
The solution from RiderOfGiraffes is brilliant, ensuring a fixed amount of tries (14) with just 2 eggs.
Also, if there are more than 2 eggs ever, the extra eggs can be used to do binary search, reducing the total # of steps by half every time. Forexample: with 3 eggs, we can use one to reduce the steps to 50, and use the second egg with steps of 10, 9, 8, etc., and the last egg to find the actual step within that block going one step at a time. If there is any luck (if the first egg doesn’t break at step 50, the time gets even better.)
Just gotta say the solution here is brilliant. That is all.
1. I cannot start on any floor above 2, because if the first egg breaks I cannot solve the problem.
2. I cannot skip more than one floor at a time:
If the egg doesn’t break on floor x, but it breaks on floor x+y (the next lowest floor tested greater than x), I only have ONE egg left to determine exactly which floor it is from the series: {x;x+1;…;x+y-1}
Since we already tested floor x, and we cannot risk breaking the last egg with uncertainty still in play, this series must be equal to {x;x+1}. In other words, x+y-1=x+1 or y=2
Therefore, we can ONLY skip one floor at a time.
Thus the worst case scenario would be 51 if the limit is 98 or 99 floors
And the total number of tries required to determine the floor with 100% certainty is floor(x/2)+2