aloalgoTwo Egg Problem
Medium
You are in a building with n floors and you have two identical eggs. You need to find the threshold floor F, which is the highest floor from which an egg will not break when dropped. We can assume 0 <= F <= n.
The properties of the eggs are:
- An egg that survives a fall can be used again.
- A broken egg must be discarded.
- The effect of a fall is the same for all eggs.
- If an egg breaks when dropped from floor
x, it will also break when dropped from any floor higher thanx. - If an egg survives a fall from floor
x, it will also survive a fall from any floor lower thanx.
Your task is to determine the minimum number of drops required to find the threshold floor F in the worst-case scenario.
Example 1
Input
10
Output
4
Explanation:
With 10 floors, the optimal strategy is to drop the first egg from floor 4.
- If it breaks, you use the second egg to check floors 1, 2, and 3 one by one. The worst case is 1 (drop at 4) + 3 (drops at 1,2,3) = 4 drops.
- If it survives, you have 2 eggs left and 6 floors remaining (5 to 10). The next drop should be from floor 4 + 3 = 7. In the worst case, 4 drops are needed.
Example 2
Input
100
Output
14
Explanation:
For a 100-story building, the minimum number of drops required in the worst case is 14.
Example 3
Input
2
Output
2
Explanation:
With 2 floors, you drop from floor 1. If it breaks, F=0 (1 drop). If it survives, you drop from floor 2. If it breaks, F=1. If it survives, F=2. The worst case is 2 drops.
Input
10
Output
4