Question
You are given 2 eggs.
You have access to a 100-storey building.
Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process
Analysis
Most obvious solutoin is drop in 10th, 20th, 30th … floor. But this solution would result in 19 drops in worst case. We should try to reduce the worst case scenario by making all possible scenarios take the same number of drops!
The best solution is:
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.
According to the solution, we form a series:
x + (x-1) + (x-2) + (x-3) + … + 1 = 100
x(x+1)/2 = 100
x = 14
Final Result
We would drop in this way:
| 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 |