## 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.

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…

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…

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

• Mike Lloyd

In any programming language,
I could loop through the main 33 floor_number variables
and formulate the result based on the strategy below.
I will find the loop exit, along with the floor_number var, while asking if function(floor_number) = false; (egg breaking) .

• Mike Lloyd

Since we have 2 eggs, I should start with the 3rd floor. If it fails, I could try 2 and know if it was 1, 2, or 3. If it succeeds I can try 6… if that fails I can try 5 (or 4), and know if the threshold is floor 4 or 5.

… and so on.

The minimum possible tries with this strategy : 2
– floor 3 fails… and 2 breaks or not

The maximum possible tries (or the minimum/maximum worst case) = 34

proof:
floor 1 was guaranteed by the threshold definition
99 / 3 = 33
33 + 1 = 34 – for the extra egg that is required to test each set of three
If it’s not 99, than it’s 100

• Mike Lloyd

P.S.

Also, what is the minimum number of drops for the worst case using this strategy?

Well if you had infinite test eggs, than the math & strategies here are super helpful! If you had one egg, the worst case is 99 drops…. but since you have 2 eggs, surprise – it has to be 99 still. the extra egg doesn’t help.

• Mike Lloyd

I believe that the answer/response must be:

“I believe that it would be best, if I start at the bottom, and work my way up – one floor at a time.” (kind of ingeniously proverbial (on their part))

– Although this strategy doesn’t reduce the drops, in any way,
– it is the only way to def
achieve success.
– and after you succeed in finding the result that is
required, with not only minimum risk, but guaranteed success…
– You will
still have one egg intact at the end.
– So, in case you ever run into a problem like this again, it’s like a get out of jail free card 🙂

What do ya think?

• 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..