hardDynamic Programming 2DPure DSA~50 min
Minimum Drops to Find the Critical Floor
You have k identical eggs and a building of n floors. There is a threshold floor above which eggs break; you want to find it using the fewest worst-case drops, reusing eggs that survive.
Problem
Given k eggs and n floors, find the minimum number of drops needed in the worst case to determine the highest floor f (0 <= f <= n) from which an egg does not break. An egg that breaks cannot be reused; one that survives can. Return that minimum worst-case number of drops.
Input
Two integers k (eggs) and n (floors).
Output
An integer: the minimum number of moves in the worst case.
Constraints
- 1 <= k <= 100
- 1 <= n <= 10^4
- Worst-case (adversarial) outcome of each drop.
Examples
Example 1
Input
k = 1, n = 2
Output
2
With one egg you must try floors bottom-up: worst case 2 drops.
Example 2
Input
k = 2, n = 6
Output
3
Two eggs over six floors need 3 drops in the worst case.