Suppose that there is a building with 100 floors. You are given 2 identical eggs. The most interesting property of the eggs is that every egg has it’s own “threshold” floor. Let’s call that floor N. What this means is that the egg will not break when dropped from any floor below floor N, but the egg will definitely break from any floor above floor N, including floor N itself.

For example, if the property of the eggs is that N equals 15, those eggs will always break on any floor higher than or equal to the 15th floor, but those eggs will never break on any floor below floor 15. The same holds true for the other egg since they are identical.

These are very strong eggs, because they can be dropped multiple times without breaking as long as they are dropped from floors below their “threshold” floor, floor N. But once an egg is dropped from a floor above it’s threshold floor

Here is the puzzle: What strategy should be taken in order to minimize the number of egg drops used to find floor N (the threshold floor) for the egg? Also, what is the minimum number of drops for the worst case using this strategy?

Remember that you are given 2 identical eggs which both have the same exact threshold floor.

This interview riddle has been asked at many major companies like Google, Microsoft, Accenture, and even Hewlett Packard – and it’s a great one to practice your problem solving skills with.

Using The Binary Search Method

Your first instinct (especially if you are a programmer) may be to solve this problem using the binary search method. So, you think that maybe by dividing the “result set” in half each time you will be able to solve the problem and find the threshold floor for the eggs. In this case the “result set” is the floors in the building, so you start at floor 50 since that is half of 100.




Let’s say we do start at the 50th floor, then what should we do if the egg breaks? This means that the answer is somewhere between the first and 50th floor. And we would be left with only 1 more egg since we started with 2 eggs. Now if we are following the binary search method, it seems that the next step would be to try dropping the remaining egg from the 25th floor. But what if it breaks at the 25th floor? Then we really don’t have an answer to the problem since we have not found the threshold floor for the eggs. Even if it doesn’t break and we decide to go to the next floor (which would be half of 25 or 12.5, which is approximately 13), then if it breaks at the 13th floor then we would still not have an answer to the problem.

Clearly the binary search method does not work for us here, because we only have 2 eggs. The binary search method would be good in a scenario where we have an infinite number of eggs, but we now have to change our strategy and find a better solution.

A new solution

Since we have to find the answer with 2 eggs then why not do something like this: we start by dropping one of the eggs on the 10th floor: if it doesn’t break then we continue on to the 20th floor, then 30th, 40th… up to 100 in intervals of 10 until the first egg actually breaks. If the egg breaks on the 10th floor then we know that the threshold floor must be either the 10th floor or one of the floors below it – the egg will definitely break on any floor above the 10th floor, so we can eliminate all of the floors above the 10th.

If the egg breaks on the 10th floor…

So, the answer must be between floors 1 through 10. We can take the 2nd egg and drop it from the first floor. If it does not break on the first floor, but it does break on the 2nd floor, then we know that the 2nd floor is the “threshold” floor. And if it doesn’t break on any of the floors between 2-8, then we just continue up until the 9th floor, and if it does not break on the 9th floor then we know that the 11th floor is our threshold floor. This will take a maximum of 10 drops to figure out the threshold floor in this instance.

What about the worst case solution? Well, the worst case using this method occurs when the threshold floor is the 100th floor. This means that we use 10 drops to get to the 100th floor, because we start from the 10th floor and go up in intervals of 10 up to the 100th floor, and the first egg will break on the 100th floor. And then we use another 9 drops with the 2nd egg because we have to test floors 90-99 to see if the threshold floor is somewhere in that range. This gives us a total of 19 drops, which is the absolute worst case scenario using this method.

Use the linear search method for this brainteaser

The simple search method we used above is called a linear search – which is simply a sequential search to find a particular value in a list of elements. In this case, the list of elements are floors in a building, and the value we are searching for is the threshold floor in that building for the eggs.

It should be clear to you now that a linear search is indeed necessary with the 2nd egg because we can not risk breaking the 2nd egg before we even find the answer – remember we only have 2 identical eggs and we must find the answer with only 2 eggs. This means that we have some freedom with the 1st egg, and that we can do some interesting work with it. So, now the question is can we improve upon the 19 drops used in the worst case scenario with our approach above?

2 Eggs 100 Floors Puzzle Solution




We want to minimize the number of drops for the worst case, while still using an approach that works well for other scenarios. So, how can we do this? Well, we should rephrase that question and ask ourselves what is really holding us back here? The main reason why it takes such a large number of drops in the worst case with our approach above (19 drops) is because in order to test out the higher floors of the building we have to start at the lower floors of the building, and at that point we have already used a large number of drops just to get to that point.

What we should try to get with our next approach is to try to reduce the worst case scenario by trying to make all possible scenarios take the same number of drops.

What if we tried to reduce the number of drops that would be required with the linear search (with the 2nd egg) after we get to one of the higher floors? This way we counteract the fact that getting to the higher floor took so many drops, and if we use less drops for the linear search we are balancing out the worst case.

Let’s try to figure this out using some simple algebra. Suppose we drop an egg from floor x. If the egg breaks, then we would have to go through the previous x-1 floors one by one using a linear search.

But, if the egg doesn’t break, in our original algorithm we would go up x floors to find the next floor to test from. Why not just go up x-1 floors instead of x floors? This would save us 1 drop if we have to do a linear search with the 2nd egg whenever the first egg breaks – because we would be doing the linear search from floors x+1 to floor ( (x+1) + (x-1)) instead of floors x+1 to floor (x+1) + x. So, that is 1 less egg drop. This means that the next floor that should be attempted to drop from is x + (x-1) if the egg does not break from floor x. And by the same reasoning the floor after that would be x + (x-1) + (x-2) if the egg does not break on floor x + (x-1).

This would go on to form a series that looks like this:

x + (x-1) + (x-2) + (x-3) + ... + 1

The series above is what’s called a triangular series which is equal to x(x+1)/2. Because there are 100 floors in the building, we set the sum equal to 100 to solve for x:

x(x+1)/2 = 100

When the sum of the series above equals 100, we get x = 13.651, which rounds up to 14. This means that we should start from floor 14 (which is our x) and then move up x-1 (13) floors to floor 27 if the egg doesn’t break and then move up x-2 (12) floors to floor 39 and so on if the egg still does not break.

This is the number of drops required as we move up the floors in the building:


 Drop   Floor 
#1 14
#2 27
#3 39
#4 50
#5 60
#6 69
#7 77
#8 84
#9 90
#10 95
#11 99
#12 100

2 Eggs 100 Floors Worst Case Solution

The solution for the worst case in this scenario occurs when the threshold floor is floor number 14 – because we will drop the first egg on floor 14, and it will break. Then we have to test floors 1-13 with the 2nd egg to see where the egg breaks again, and the egg will not break on any of those floors. But since the egg broke on the floor 14, we can conclude that the threshold floor is floor number 14.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • kigo

    Hi. Nice explanation.
    So you suggest a solution. How you prove that is the best solution .. maybe is a better solution then that?

  • venkat

    OK I agree. Thanks Bharath

  • Bharath

    What if the egg breaks in 1st floor only. U would have no way of knowing since both eggs r used in 13 & 14th floor

  • venkat

    worst case solution is wrong. Because if first egg breaks at floor 14 means we have to try 13th floor with second egg. Second egg is not been broken in 13th floor because 14th floor is threshold floor..so no need of checking remaining 1-12 floors..within two steps we could find the answer..

  • Md Farooq

    awesome solution

  • Pecanac

    I am amused by the complicated answers for this problem 😀 I just love the nerds – (not being sarcastic) 🙂
    I would answer like this: you drop it from the 1st floor. If it doesn’t break, drop the other (pristine) egg from the 2nd floor – it almost HAS to break. But if even the second floor doesn’t break the egg, it is safe to say the 3rd definitely will.
    I mean we’re not talking about rocks or some cartoon magical eggs here people 🙂

  • Perfect solution,..very nice.. Before this it was known to me best solution as 19.

  • gekaprog

    Two things are missing;
    1. It’s not clear how the author arrived at the solution except by brute force. No algorithm presented and no proof that 14 is best.
    2. Extending on first point. If I gave you a computer, write a program that finds a minimum number of drops from floor Y.

  • Ray Morris

    This is a very interesting algorithm, but a poor solution to the problem as presented. It is known eggs normally break when dropped from 4 feet (half a floor). Therefore an optimal solution would be approximate simple linear search – we know empirically that eggs will break much lower than floor 50. We should therefore optimize for the near-certain case that eggs continue to break when dropped from low dloors – just as they always have.

    The algorithm presented would be appropriate for testing how high an unknown object could be dropped without breaking. (Or eggs in very padded containers

  • ravi

    great…Thank you…

  • Addie

    wrong

  • Manohar Bhat

    but no of drops in worst case is 50 which is very high. (This happens in case threshold floor is 49)

    Our goal is to minimize no of drops in worst case.

  • gyeaaaa

    only works if u have infinite eggs…

  • Bijay Kumar Yadav

    Well explained. Thank you.

  • Ashwini Singh

    Simple. Drop Egg from 1st Floor, if it breaks then end of puzzle.
    Otherwise drop from floor 50. If it does not break then you will know that threadhold height is still to be reached and start dropping 2nd Egg from 51.
    Effective as you have surpassed all the below stories.
    In case it does break at floor 50, all you need to do is starting dropping from Floor 2 till you reach breaking point

  • Archit Kapoor

    You may be forgetting a ground floor. Much is to imagine. Puzzles like these are to assess how you approach a problem statement. It is not always possible to reach the correct solution but then you make your brain cells work, better and faster if you are a programmers. And that’s tested with these kind of questions

  • Michael Legel

    1 floor … what kind of egg doesn’t break if you drop it from the second floor much less a counter top? And how would you drop an egg below the first floor? From the basement? Evidently practical applications mean nothing to programmers?

  • Nicely explained..