Super Egg Drop
Hard · Dynamic Programming · Math · Binary Search · Dynamic Programming
Problem
You have k identical eggs and a building with floors 1 to n. There is an unknown floor f (0 <= f <= n): an egg dropped from any floor above f breaks, and one dropped from floor f or lower survives.
In one move you drop an unbroken egg from a floor of your choice. A broken egg cannot be used again; an egg that survives can.
Return the minimum number of moves that guarantees you find f, whatever its value.
Examples
Input: k = 1, n = 4 Output: 4
With one egg you must test floors 1, 2, 3 and 4 in order.
Input: k = 2, n = 10 Output: 4
Four moves with two eggs settle 4 + 3 + 2 + 1 = 10 floors: drop from 4, then 7, 9, 10, stepping down with the second egg after a break.
Input: k = 3, n = 14 Output: 4
Three eggs and four moves settle exactly 14 floors; three moves settle only 7.
Constraints
- 1 <= k <= 100
- 1 <= n <= 10^4
Approaches
- Baseline: moves per (eggs, floors) with a binary search — time O(k · n log n), space O(k · n)
Follow-up
The table of floors per (eggs, moves) is a sum of binomial coefficients, reach(e, m) = C(m, 1) + ... + C(m, e), which answers "how many floors can m moves cover" directly. The use cases ask that, and the classic two-egg puzzle.
Related problems
Start free on Cariara · Coding problems · System design studio
