easy | strategy |
An Egg breaks only if dropped from above a threshold floor, within a 100-story building. Every time you drop an egg, it is counted as an attempt. You are given 2 eggs to deduce the threshold floor, with a minimum number of attempts in the worst case!
If we had only 1 egg, we would go linearly from 1 to 100. Having an extra egg allows for skipping some floors. When 1st egg breaks, the second egg can move linearly.
It can be done in 14 steps in the worst case.
We can skip some floors and jump ahead when testing with the first egg (egg1). Whenever egg1 breaks, egg2 has to scan linearly from the last safe floor to the floor where egg1 broke.
For example, we can test floors 10, 15, 20 and so on. Suppose egg1 broke at the floor, now we need to test from 16 to 19, which can be done one by one using the second egg (egg2). But this is suboptimal, because regardless of when egg1 breaks, egg2 is always taking 4 attempts. We can improve this algorithm by reducing the length of the gap on each attempt of egg1.
For instance, if we test at floor 10, 10+9, 10+9+8, and so on, then in the worst case, the number of attempts will be at-most (1+9)=10 or (2+8)=10 and so on... But, there's a problem, this sequence ends at and does not span the entire range of 100 floors. But the idea is in the right direction.
A solution for minimum steps in the worst case is the smallest integer greater than or equal to the positive solution of
Start at floor 14, if the egg breaks start linearly from 1, if it does not break then drop the egg from floor, and so on. The following table can be constructed.
Egg1 Attempt | JumpSize | Egg1 Floor | Egg2 max attempts | Total Attempts |
---|---|---|---|---|
1 | 14 | 14 | 13 | 14 |
2 | 13 | 27 | 12 | 14 |
3 | 12 | 39 | 11 | 14 |
4 | 11 | 50 | 10 | 14 |
5 | 10 | 60 | 9 | 14 |
6 | 9 | 69 | 8 | 14 |
7 | 8 | 77 | 7 | 14 |
8 | 7 | 84 | 6 | 14 |
9 | 6 | 90 | 5 | 14 |
10 | 5 | 95 | 4 | 14 |
11 | 4 | 99 | 3 | 14 |
12 | 1 | 100 | 0 | 12 |
This ensures at-most 14 attempts.