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 [email protected]. If you have any interview questions which you feel would benefit others, I would love to hear about it.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
=> n+(n-1)+(n-2)+(n-3)+….(n-n) = 100
=> n(n) – n(n+1)/2 = 100
=> n^2+n-200 = 0
=> n=-[-1 +- (28.3)]/2
=> n = 14
On the 2 egg problem, I may be mistaken, but I think I can improve upon the given answer.
Once the first egg has broken, and you can skip a floor after each drop. If the egg breaks,
you know the floor under it is the highest floor that an egg can be dropped from since the floor
below that one was already tested. You may end up with two broken eggs, but there is no
reason to test the correct floor once the floor above and below it have been tested. If the problem
wouldn’t have specified that “One of the floors is the highest floor an egg can be dropped from
without breaking”, then this solution wouldn’t work.
# highest floor an egg won’t break from
13
# floors we drop first egg from
14
# floors we drop second egg from
2, 4, 6, 8, 10, 12
# total number of drops
7
# highest floor an egg won’t break from
1
# floors we drop first egg from
14
# floors we drop second egg from
2
# total number of drops
2
# highest floor an egg won’t break from
98
# floors we drop first egg from
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99
# floors we drop second egg from
96, 98
# total number of drops
13
Actually if you use that technique, it changes how we should drop the first egg as well. Making the highest number of drops 10.
First drop should be at 20, if it breaks, drop from floor 2,4,…18. The first egg, plus the second egg gives a total of 10 drops.
Then add n-2 if the first egg does not break, drop it from floor 38, the second egg will be dropped at floors 22,24,…36. The first egg has been dropped twice, and the second egg has been dropped eight times.
In the worst case for the first egg, floor 99 or floor 100, the first egg would drop 9 times.
The 9th drop would be on the 98th floor. The same egg (since it didn’t break) or the second egg could then be dropped at the 100th floor.
this would be 10 total drops. If it breaks on the 100th floor, then the 99th floor is the highest, if it doesn’t, then floor 100 is the highest.
Thanks for taking the time to read this, if there is something wrong with my solution please let me know!
If it breaks at 50, move on to 25. If it breaks at 25, you are out of eggs now. Now how do you find the solution? 🙂
nice solution
but v hv only 2 eggs,, so minimum try can be 2 only………..
Unless I am understanding the question totally wrong, I can do this with 6 eggs.
My logic tells me 6 minimum, but likely 7. I will start at floor 50, and if it breaks, I go to floor 25. If it breaks again, I go to floor 12, or if it doesn’t, I go to floor 37, etc. In essence, I go the half of the distance (rounded up) between the last two trials, until I get to floor n. See example below:
Start: Floor 50. It breaks.
Go to: Floor 25. It breaks.
Go to: Floor 13. It does not break.
Go to: Floor 19. It does not break.
Go to: Floor 22. It breaks.
Go to: Floor 21. It breaks.
Go to: Floor 20. It does not break.
Does this not make logical sense? Or where am I going wrong?
Kobus
The problem is that performing the test affects the results. If you drop the egg from floor x and it survives, it is definitely weakened to the point of ruining the second time it’s dropped. So there is no way to solve the problem.
It is simple. Drop egg from 100th floor. For the first 99 floor it wont break. And that’s the answer…:)
Idiots … you can drop eggs from any floor without breaking … it will break only when it reaches ground … and i need no tries for it .. i simply know it ….. Fools .. 😉
The answer is not 19 . It can be found in 18 tries.
Lets first start with a stepping of 10.
So, I will try it at 10,20,30,40,50,60,70,80,90
that takes 9 tries.
Now at 90 two things can happen either the egg will crack or not :
Case 1 – egg got cracked so i am left with only one egg and I have to check the range from 81 to 89 .So, now I will have to test 81,82,83,84,85,86,87,88,89 that again takes 9 tries. so total of 9+9=18 tries.
Case 2 – Egg didn’t break so i am still left with 2 eggs. so I will try at 95 if it get break then I will try 91,92,93…. else I will try at 96,97,…… so it will take 9+ 1+5 = 16 tries to determine.
So, considering maximum among these two condition we need min 18 tries to find out.
The answer is 1.
Dropping one egg from the first floor will break it. At this point you’ll know that there is 0 possibility of dropping an egg from any floor without breaking it. Plain simple.
What types of eggs can withstand a 98-story fall? Easter eggs?
In the Update answer, the minimum number of tries, 14. is a number that implies that the first dropped egg, the test egg, will not break until the top floor (floor 105 in the Update even though the problem has 100 floors).
If the egg did break on the first drop, the 14th floor, after that there’d be no way to find out the maximum floor the egg can survive since you have only one more egg.
Start from the first floor and drop the egg (ie x = 1).
If the egg breaks
then the maximum number of floors from which the egg can be dropped without breaking is 1.
Else If egg doesn’t break,
move on to the 4th floor (ie every time you go to plus 3 floors ie x = x+3) and drop the egg.
If the first egg breaks at 4th floor
then move to the 2nd floor and drop the second egg.
If the second egg breaks,
then the maximum number of floors from which the egg can be dropped without breaking is 1.
Else if the second egg doesn’t break in 2nd floor
then move to 3rd floor and drop the second egg.
If the egg breaks,
the maximum number of floors from which the egg can be dropped without breaking is 2.
Else if the egg doesn’t break
then the maximum number of floors from which the egg can be dropped without breaking is 3.
Else if the first egg doesn’t break at 4th floor
Go to 7th floor (plus 3 floors ie x = x+3) and drop the egg.
The Minimum number of tries needed would be 100/3 = 33 tries.
@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