541. Super Egg Drop
You are handed k identical eggs and stand before a building whose floors are numbered 1 to n. The building hides a threshold f, with 0 <= f <= n: an egg dropped from any floor above f shatters, while an egg dropped from floor f or lower survives and can be dropped again. A shattered egg is gone for good.
On each move you choose a floor and drop one egg from it. You must determine f with certainty — the answer has to be correct for every possible threshold, including f = 0 (eggs break everywhere) and f = n (eggs never break).
Your function receives the integers k and n and returns the minimum number of moves that guarantees identifying f, no matter where it hides.
Example 1:
Input: k = 1, n = 2
Output: 2
Explanation: With a single egg you cannot risk skipping floors. Drop from floor 1: a break means f = 0. If it survives, drop from floor 2: a break means f = 1, a survival means f = 2. One move can never separate three possible outcomes.
Example 2:
Input: k = 2, n = 6
Output: 3
Explanation: Open at floor 3. If the egg breaks, walk the remaining egg up floors 1 and 2 — two more moves. If it survives, drop from floor 5; a break sends the last egg to floor 4, a survival sends it to floor 6. Every branch finishes within 3 moves, and no 2-move plan can distinguish all 7 outcomes.
Example 3:
Input: k = 3, n = 14
Output: 4
Explanation: With 3 eggs and 4 moves you can handle exactly C(4,1) + C(4,2) + C(4,3) = 14 floors, so 4 moves suffice for 14 floors — and 3 moves cover at most 7.
Constraints:
- 1 ≤ k ≤ 10
- 1 ≤ n ≤ 1000
Hints:
Think in states: (eggs left, floors still suspect). Dropping at height x inside a suspect stretch splits it — a break leaves x - 1 lower floors with one egg fewer; a survival leaves the floors above x with all your eggs. The adversary always hands you the worse branch.
For a fixed state, as the drop height x rises, the break branch gets worse and the survive branch gets better. The two curves cross once — you can binary search the balance point instead of scanning every x.
Invert the question entirely: with m moves and e eggs, how many floors can you conquer? cover(m, e) = cover(m-1, e-1) + cover(m-1, e) + 1 — floors below the drop, floors above it, plus the drop floor itself. The answer is the smallest m with cover(m, k) >= n.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: k = 1, n = 2
Expected output: 2