there is a building of 100 floors -if an egg drops from the nth floor or above it will break. -if it’s dropped from any floor below, it will not break. you’re given 2 eggs. find n how many drops you need to make?
Answers
Brute Force logic:
Start from ground floor and keep going up until the egg breaks at floor X.
Solution is very inefficient, in case the egg doesn't break till the 99th floor.
Remember, you need to minimise the number of drops in the worst case.
Improvised solution:
Start from the 10th floor and go up to floors in multiples of 10
If first egg breaks, say at 20th floor. then you can check all the floors between 11th and 19th with the second egg to see which floor it will not break.
In this case, the worst-case number of drops is 19. If the threshold was 99th floor, then you would have to drop the first egg 10 times and the second egg 9 times in linear fashion.
Best solution:
We need to minimize this worst-case number of drops. For that, we need to generalize the problem to have n floors. What would be the step value, for the first egg? Would it still be 10? Suppose we have 200 floors. Would the step value be still 10?
The point to note here is that we are trying to minimize the worst-case # of drops which happens if the threshold is at the highest floors. So, our steps should be of some value which reduces the #of drops of the first egg.
Let's assume we take some step value m initially. If every subsequent step is m-1,
then,
m+m−1+m−2+.....+1=n
This is m∗(m+1)2=n
If n =100, then m would be \ceil13.65 which is actually 14.
So, the worst case scenario is now when the threshold is in the first 14 floors with #of drops being 14.