## Interviewing Question: The Eggs and the Tower

Posted by archworx on February 19, 2007

Think of this, you have a building which is **100** floors high and you have **3** eggs. You can throw an egg from any floor and it might or might not break, but there is a certain floor (a threshold floor) afterwhich eggs are guranteed to break for all floors above this certain floor. If We want to know exactly which floor is the threshold floor, **what is the minimum number of egg throws do we have do make? **

**Remember**: You have only **3** eggs, so if you break all the 3 eggs without finding the threshold floor then you have failed. Also remember that we want the **minimum **number of throws.

Advertisements

## Mohamed Fouad said

zero!!

## archworx said

MMK: I just asked the author of this question, and he says that the fact that it is an egg (and can break very easily) is immaterial. It could be a piano or a marble egg or anything else for that matter. So the answer will have to rely on algorithmic intelligence.

So what will it be?

## yshahin said

I think that to solve the problem we should consider that the building is an bool array that says false except for the floor that we need therefore we can just use any search algorithm on the array that will give us the location of the cell with the true in it

## yshahin said

I think that to solve the problem we should consider that the building is an bool array that says false except for the floor that we need therefore we can just use any search algorithm on the array that will give us the location of the cell with the true in it

but then the problem becomes which search algorithm will give us the best result based on the fact that we only have 3 eggs

## Ahmed Fathalla said

Your close YShahin,

It is indeed a searching problem. But I think the fact that it is a bool array not very relevant. I’d like to think of it as an int array ordered ascendingly…Hahaaaaa…..that’s a cool hint isn’t it..so can anyone come up with the answer!!

## Mohamed Fouad said

Min Number = Floor Number + 1 !!

## Mohamed Fouad said

..any floor and it might or might not break(uncertainty)+2?!

its an egg question 🙂

## David Ching said

I think this problem is not solvable. Even if you went to the 100th floor and dropped all 3 eggs and they all broke, it doesn’t guarantee all eggs will break on the 100th floor. This is because an egg breaking doesn’t set the threshold since “at any floor, it might or might not break” and the 4th egg you dropped might not break.

## yshahin said

Ahmed Fathalla

it doesn’t have to be an int array because if i understand what your thinking

you want an int array for counting the floors

and the index is our counter the bool is just to identify the break point

and David Ching i think that your talking about the philosophy of the problem.

Just assume that they all have the same threshold and what happens to one will happen to the other under equal conditions

I think the answer is 4 Throws

## David Ching said

OK I was misreading the problem and believe I understand now. Well, the Computer Science way is to do a binary search, so log(2)100 = 7 eggs. But if we only have 3 eggs, we can’t do a straight binary search, since we might break 6 eggs before we found the threshold.

Since we only have 3 eggs, the safe way is to start on Floor 1, try it, if it doesn’t break, go to Floor 2, try it, repeating until the egg breaks, and that is the threshold floor. But if that is Floor 100, it would take 100 tries.

So what if we start with the binary search, until we break 2 eggs. Then since we have only one left, we need to switch to the safe way. The worst case is we break 2 eggs immediately, during the binary search. At this point, the binary search will have reduced the possibilities by 4, so there are 25 floors still to check. We switch to the safe way and try up to 24 floors.

So the worst case is 2+24 = 26 tries, guaranteeing we don’t break more than 3 eggs.

## Mohamed Fouad said

yes, thats the simple Data structre problem and solution. anyway 7asal 7’ee r 🙂 any cool hypothetical questions for tommorw 🙂

## fathalla said

Excellent contribution Mr.David, actually there is a better answer where we can get it in 12 throws 🙂 Can you think about it !!!

N.B. Thank you for being an active contributor on our blog 🙂

## Mohamed Fouad said

from ground-up, on every 10 floors boundries.

and we can only hope that the tower got an elevator 🙂

Thanks, Fathalla Basha!

## David Ching said

Thank you Fathalla, these questions are a lot of fun. I was wondering if you are really interviewing and need the answers? 🙂

I can’t think of how to do it in 12 tries, will think some more. Or just tell us! 🙂

Cheers,

David

## fathalla said

Its nice to have received all these comments on this post. Now, it’s time to reveal the answer. 🙂

I think the best worst case is 12 throws . The key here is dividing by 3. So Imagine you threw the first egg off the 33rd floor and it broke. Divide by 3 and throw it off the 11th floor, it breaks. Now we know for certain that the threshold floor is between 1 and 11. Now, since you have only one egg, you go sequentially from the first floor to the 10th floor. In the worst case this would mean 10 more throws, add those to the original 2 throws where you broke the 2 eggs. This would give a sum of 12 in the worst case. I think this is the best worst case achievable under all scenarios.

## David Ching said

Clever Fathalla! 🙂

But consider, what is the “worst case”? Both our solutions assumed it is when the eggs break right away, which forces us to the “safe way” earlier and thus use more throws on the safe way.

But what if the worst case is when the eggs don’t break? Here, the binary search eliminates the most floors per try and has an advantage over dividing by 3.

It seems if the first egg breaks, your answer will have less throws, but if not, then my answer will have less throws, since you have 67 more floors to test, and I have only 50. So if the threshold floor is evenly distributed (i.e. it can be any floor with equal probability), then you have a 33% chance of winning, and I have a 67% chance of winning.

And math was never my strength! 🙂

Cheers,

David

## Mohamed Fouad said

it can be done in 6

## sourav said

it can be done in 9 ways… think of this formulae {(n)*(n+1)}/2

## Adam said

I’ve found a few ways to solve it with 10 drops as an absolute worst case. The trick to trying to minimize your attempts is to narrow it down as best you can with the first 2 eggs, because you are forced to do a sequential search with the final egg.

## Rick said

At EVERY floor before the threshold floor the egg WILL NOT break. So you can keep using it. You only need 1 egg.

## BAdel said

@ Rick

I think that sol. is the answer ..

## Vikram said

Rick, your answer would have been correct if the question was to find out the minimum number of eggs required.

The Question however, is to find out the minimum number of throws needed to find out the threshold floor. If the threshold floor is the 100th floor and we start from the first then we need 100 throws, which is not minimum.

## tony said

mine 50 10 20 30 40 31 32 33 34 35 36 37 38 39 worst case 14

fathalla 33 66 44 55 45 46 47 48 49 50 51 52 53 54 worst case 14 (i think) because I dont think you would do floor 99 and I dont know what your approach would be for floors 67-100

var threshold;

var floors = new Array();

var trys = new Array();

var stories = 100;

for(i = 1;i <=stories; i++)

floors.push(i);

for(threshold = 1; threshold 1){ // two eggs left

while(eggs > 2){ // three eggs left

broken = false; // we don't want the outer loop to run immediately

floor = Math.ceil( ( upper - lower ) / 2 ) + lower; //binary

if(floor > threshold){

trys[threshold-1]++;

if(quick){ // one egg left

eggs=1;

}else{

eggs--;

broken = true;

upper = floor;

}

}else if(floor = upper){ // last 9 numbers to check

quick=true;

eggs = 3;

broken = false;

}else{

if(floor > threshold){

trys[threshold-1]++;

eggs--;

}else if(floor < threshold){

trys[threshold-1]++;

lower = floor;

}else{

lower = floor - 1;

eggs = 1;

}

}

}

broken=true; // start running outer loop

}

lower++;

trys[threshold-1]++;

}

}

document.write("floortrys");

for(i = 0; i < floors.length; i++)

document.write("" + floors[i] + "" + trys[i] + "")

document.write("");

## tony said

doh well the formatting disappeared, it is written in javascript and the document.write is missing the table formatting. and some variables disappeared

## Sharad said

The correct (optimal) solution for this is 12 drops.

FOR EGG 1:

======================

1st drop : 36th floor

2nd drop : 64th floor

3rd drop : 85th floor

4th drop : 100th floor

If egg1 breaks at 36th floor: ( EGG 2 )

==========================================

5th drop : 0 + 8 = 8th floor (for egg3 worst case: + 7 drops = 12 drops)

6th drop : 8 + 7 = 15th floor (for egg3 worst case: + 6 drops = 12 drops)

7th drop : 15 + 6 = 21st floor (for egg3 worst case: + 5 drops = 12 drops)

8th drop : 21 + 5 = 26th floor (for egg3 worst case: + 4 drops = 12 drops)

9th drop : 26 + 4 = 30th floor (for egg3 worst case: + 3 drops = 12 drops)

10th drop : 30 + 3 = 33rd floor (for egg3 worst case: + 2 drops = 12 drops)

11th drop : 33 + 2 = 35th floor (for egg3 worst case: + 1 drops = 12 drops)

If egg1 breaks at 64th floor: ( EGG 2 )

==========================================

5th drop : 0 + 43 = 43th floor (for egg3 worst case: + 6 drops = 11 drops)

6th drop : 43 + 6 = 49th floor (for egg3 worst case: + 5 drops = 11 drops)

7th drop : 49 + 5 = 54th floor (for egg3 worst case: + 4 drops = 11 drops)

8th drop : 54 + 4 = 58th floor (for egg3 worst case: + 3 drops = 11 drops)

9th drop : 58 + 3 = 61st floor (for egg3 worst case: + 2 drops = 11 drops)

10th drop : 61 + 2 = 63rd floor (for egg3 worst case: + 1 drops = 11 drops)

If egg1 breaks at 85th floor: ( EGG 2 )

==========================================

5th drop : 0 + 70 = 70th floor (for egg3 worst case: + 5 drops = 10 drops)

6th drop : 70 + 5 = 75th floor (for egg3 worst case: + 4 drops = 10 drops)

7th drop : 75 + 4 = 79th floor (for egg3 worst case: + 3 drops = 10 drops)

8th drop : 79 + 3 = 82th floor (for egg3 worst case: + 2 drops = 10 drops)

9th drop : 82 + 2 = 84th floor (for egg3 worst case: + 1 drops = 10 drops)

If egg1 breaks at 100th floor: ( EGG 2 )

==========================================

5th drop : 0 + 90 = 90th floor (for egg3 worst case: + 4 drops = 9 drops)

6th drop : 90 + 4 = 94th floor (for egg3 worst case: + 3 drops = 9 drops)

7th drop : 94 + 3 = 97th floor (for egg3 worst case: + 2 drops = 9 drops)

8th drop : 97 + 2 = 99th floor (for egg3 worst case: + 1 drops = 9 drops)

Hence, in the worst case, you need 12 drops..

## mitesh said

We need to do the following:

I. propose algorithm;

II. make upper bound estimation of number of steps.

We do not intent to proof that the algorithm is optimal in any sense, just providing some bound.

I. Algorithm

Let us fist consider at first three more simple algorithms, and the will get to our more complex and

efficient one.

1. Trivial algorithm is then we throw egg starting from floor 1 and up. Clearly we can get K steps in

worst case and don’t leverage the second egg;

2. The most obvious way of adding second egg is to throw the first egg on each even floor starting

from the ground and up, and when it will be broken check previous (odd) floor with second one.

This will take K/2 + 1 steps in worst case;

3. The next algorithm is based on observation, that we actually can break K into bigger chunks

using the first egg to significantly lower the worst case scenario. Let’s make number of chunks

equal to chunk size, so that we have 𝐾 chunks with size 𝐾. Then the worst case is then we go

through upper bounds of all (except the last one) chunks with first egg and then in last chunk we

go linearly from ground up with second egg. So we have in total 𝐾 − 1 + 𝐾 − 1 = 2 𝐾 − 2

steps which is already good but still is worse than we want to get with K big enough.

Our proposed algorithm is based on 3rd one and observation that we want to make chunks less and less

each time so that the more steps we do to find right chunks, the less time we need to go through it

linearly with the second egg. Obviously, since each next chunk top requires one first egg throw we need

each next chunk size to be smaller by one to keep worst-case scenario number of steps the same for

each chunk. And we need to ensure that 𝑐ℎ�𝑛𝑘 ��𝑧𝑒 ≥ 𝐾

��𝑒𝑡�

,Clearly since we decrease chunk size .

the last size can be just 1.So, we get the following algorithm: if x is number of worst-case steps, we throw the first egg from floor x

on step one, then from floor x+(x-1) on second step, then from floor x+(x-1) + (x-2) on third, etc.,

decreasing chunk size by 1 on each step until the last chunk will be of size 1. If the first egg is broken on

some step t0 have 2

roots. Here 𝐷 = 1 + 8𝐾 which means that one of the roots is always negative in our case, as soon as we

need only positive one we have 𝑥 =

−1+ 1+8𝐾

2

= 2𝐾 +

1

4

−

1

2

.Q.E.D .

End of the proof.

Example: For K=100 we have 𝑥 = 13.65 = 14 so we throw egg from floor 14 first, than from floor

27 = 14 + 13, than from floor 39 = 14 + 13 + 12, than from floors 50, 60, 69, 77, 84, 90, 95, 99, 100,

which are the tops of chunks. You can easily check that this will not work for K=100 and x=13 (you will

have too much floors left for the last chunk).

## Alex Min said

it can be done in 10 drops.

drop your first egg on the 50th floor. If it breaks, then you look from the 1st floor to the 50th floor. Otherwise you look from the 51st floor to the 100th floor.

let’s say the egg broke on the 50th floor.

now drop the second egg from the 10th floor, if it breaks, then try from 1st floor until the third egg breaks. = 10 tries if the egg breaks on the 9th floor.

if the second egg didnt break from the 9th floor, drop the second egg from the 19th floor…then the 27th floor.. then 34th floor…then 40…then 45…then 49.

10 drops!

## Alex Min said

it can be done in 10 drops.

drop your first egg on the 50th floor. If it breaks, then you look from the 1st floor to the 50th floor. Otherwise you look from the 51st floor to the 100th floor.

let’s say the egg broke on the 50th floor.

now drop the second egg from the 10th floor, if it breaks, then try from 1st floor until the third egg breaks. = 10 tries if the egg breaks on the 9th floor.

if the second egg didnt break from the 10th floor, drop the second egg from the 19th floor…then the 27th floor.. then 34th floor…then 40…then 45…then 49.

10 drops!