If you have 2 eggs and you want to figure out what's the highest floor from which you can drop the egg without breaking it, how would you do it? What's the optimal solution to Identify Safe Height by Dropping Eggs?
For simplicity we can assume that the building is 100 floors high.
As any other aptitude problems let us list down what we know:
- The building is 100 floors high
- We have two eggs
- We can drop the eggs as many times as possible (if it is not broken in the previous drop)
We understand that the question demands an optimal solution, but let us first find out how to even approach this problem. May be a Brute Force solution at first will help. Then we will dwell deeper and try to understand a better solution and if possible we will optimize the same.
Brute Force approch to Identify Safe Height by Dropping Eggs
In this solution we do not even need two eggs. Just one egg would suffice. The algorithm or approach is pretty naive, start from the first floor and keep dropping the egg till it does not break.
The floor at which the first egg breaks is the highest floor for a safe drop.
What is the problem with the solution?
Clearly if the highest floor for the safe drop is the top floor, we need to drop the egg 100 times. and certainly you will get tired going down stairs every time, picking up the egg and running back to one of the floors and repeating this process.
That is why it is required to have a solution which doesn't require you to climb up 100 and down 100 times in the worst case. We need something where the number of times a person needs to climb is lesser than 100 and possibly not proportional to 100 (the number of floors).
A better solution
Let us say that I just want to climb up/down 20 times and identify the highest floor for a safe drop. So, what do I do?
Let me just reach up to the 20th floor and drop one egg. Here are the two outcomes:
So what does this solution demonstrate?
- The egg breaks: In this case, I learn that I need to try from a lower floor and I cannot take chances. Now that I know an upper bound on the possible highest floor, so I can apply the Brute Force solution till 19th floor this time. This results in a maximum of 20 iterations in the worst case.
- The egg does not break: In this case, I learn that I need to try from a higher floor, I just tried one iteration by dropping the first egg. Hence I can try a maximum of 19 more iterations. So I climb up to a higher floor X such that I can find out the possible safe highest floor in not more than 19 iterations. Hence, the value of X must be 20+19 as I have already tested till 20th floor.
- Now repeat the same thing again. As I have both the eggs intact, I just drop one from the 39th floor. Exact same cases arise, if the egg breaks I need exactly 18 more drops in worst case to figure out the highest floor for safe drop.
- If the egg is still intact, I move higher and this time as I have already used two drops, I can afford only 18 more drops. Hence I reach at 20+19+18 = 57th floor.
- This continues till we find the safe floor or I reach the top floor. And in each iteration I made sure that I do not use more than 18 drops.
We can actually choose to use X number of drops. Here the question demands an optimal solution. Looking at the above approach I can figure out that if I start at floor T and if the first egg is broken then I have to test T-1 floors. Next time I test the (T+T-1)th floor and T-2 additional floors and so on.
As we chose the number of drops to be 20, we will evaluate the following floors:
- Floor 20 , I test the 20th floor first and 19 subsequent once in case the egg broke i.e. (1+19). If the egg didn't break
- Floor 39 , I test the 39th floor first and 18 subsequent once in case the egg broke i.e. (1+18). If the egg didn't break
- Floor 57 , I test the 57th floor first and 17 subsequent once in case the egg broke i.e. (1+17). If the egg didn't break
- Floor 74 , I test the 74th floor first and 16 subsequent once in case the egg broke i.e. (1+16). If the egg didn't break
- Floor 90 , I test the 90th floor first and 15 subsequent once in case the egg broke i.e. (1+15). If the egg didn't break
- Floor 105 , Because there is no such floor, hence the total tests done here will be upt0 100 floors only, but if there were extra floors it would have been (1+14) tests at max.
The above sequence of steps suggests that in an optimal solution the number of linear tests in the last step must be close to zero. Here it is 14.
Which ideally means that if I add up all the possible tests then it would be equal to or exceed the total number of floors in the building. Hence,
(1+19) + (1+18) + (1+17) + (1+16) + (1+15) + (1+14) >= 100. To generalize the same,
(1+ T) + (1+(T-1))+(1+(T-2))+(1+(T-3)) + ... +(1 + 1) + (1+0) >= 100 . If we can replace 1+T with S then we get,
S + (S-1) + (S-2) + (S-3) + (S-4) + ... + 2 + 1 >= 100
which implies S(S+1)/2 >= 100 and the minimum value of S which satisfies this equation would be S=14. Hence, the total number of optimal drops is 14 if we need to identify the highest floor for a safe drop.