Super Egg Drop
Super Egg Drop: with k eggs and n floors, find the minimum number of moves that guarantees locating the critical floor.
- 1 <= k <= 100
- 1 <= n <= 10⁴
Intuition
Super egg drop gives you k eggs and n floors and asks for the minimum number of drops that guarantees finding the critical floor — the highest floor from which an egg survives. The word guarantees matters: you are planning against the worst case, not the average.
The natural DP asks "how many drops for n floors with k eggs?" and tries every floor as the first drop, taking the worse of the two outcomes and minimising over the choice. That is O(k·n²), which is far too slow for n up to 10⁴.
The trick is to invert the question:
- Instead of asking how many drops n floors need, ask how many floors m drops can cover with k eggs.
Call that f(m, k). Now consider one drop. The floor you drop from is itself resolved. If the egg breaks, you have m − 1 drops and k − 1 eggs for the floors below; if it survives, m − 1 drops and k eggs for the floors above. Those two ranges plus the drop floor itself are everything you can cover:
- f(m, k) = f(m − 1, k − 1) + f(m − 1, k) + 1
No minimisation and no choice of pivot — the recurrence is a plain sum, which is why it is so much faster. March m upward until f(m, k) ≥ n, and that m is the answer.
Coverage grows extremely fast (these are binomial sums), so m stays small — for 10⁴ floors and a handful of eggs it is well under a hundred.
The state inversion that makes this tractable: instead of asking "how many moves for n floors?", ask "how many floors can I cover with e eggs and m moves?" That flips an expensive minimisation into a simple additive recurrence — dp[e] += dp[e-1] + 1 — and you increment moves until coverage reaches n. When a DP is too slow, try swapping an answer with a parameter.
Approach
Before reading on: price up what the brute force costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(k · answer) time and O(k) space.
See why the direct DP is too slow
dp[k][n] = 1 + min over pivot of max(dp[k-1][pivot-1], dp[k][n-pivot]) requires trying every pivot, giving O(k·n²) — infeasible for n up to 10⁴ without further optimisation.
Invert to coverage
Define f(m, k) as the maximum floors decidable in m drops with k eggs. Swapping which quantity is the unknown is what removes the pivot search entirely — the single idea the whole solution rests on.
Derive the recurrence from one drop
The drop floor accounts for 1. Breaking leaves f(m-1, k-1) floors below; surviving leaves f(m-1, k) above. So f(m, k) = f(m-1, k-1) + f(m-1, k) + 1, a plain sum with no minimisation.
March m upward
Increment m from 1, updating coverage each time, and stop as soon as f(m, k) >= n. That m is the minimum number of drops that guarantees an answer.
Keep a one-dimensional array over eggs
Since f(m, ·) depends only on f(m-1, ·), a single array indexed by egg count suffices. Update it from high egg count downward so each cell still reads the previous row's values.
Note how fast coverage grows
f(m, k) is a sum of binomial coefficients and grows nearly exponentially in m. For 10⁴ floors the loop terminates in well under a hundred iterations, which is why marching upward is practical rather than naive.
Cost of the inverted DP
Each iteration updates k cells and there are at most n iterations in the worst case, giving O(k·m) time where m is the small answer, with O(k) space.
Solution & live demo
Common pitfalls
Modelling it as a minimisation over drop floors
dp[e][n] = 1 + min(max(dp[e-1][x-1], dp[e][n-x])
for x in range(1, n + 1))while dp[k] < n:
m += 1
for e in range(k, 0, -1):
dp[e] = dp[e] + dp[e - 1] + 1The direct formulation is O(k·n²) and times out for n = 10,000. Inverting the state — floors covered as a function of moves — makes each step O(k) with no inner search at all.
Iterating eggs in ascending order
for e in range(1, k + 1):
dp[e] = dp[e] + dp[e - 1] + 1for e in range(k, 0, -1):
dp[e] = dp[e] + dp[e - 1] + 1dp[e-1] must hold the value from the previous move count. Ascending order overwrites it first, so the recurrence reads a value from the current round and overcounts — the same rolling-array hazard as 0/1 knapsack.
Returning the coverage instead of the move count
return dp[k]
return m
dp[k] is how many floors are now coverable, which is at least n. The question asks for the number of moves it took to get there.
Edge cases
Must scan bottom-up: coverage grows by 1 per move — answer n.
One drop decides — answer 1.
With k ≥ log₂n eggs it degenerates to binary search: ⌈log₂(n+1)⌉ moves.