On this page
Description
You have k eggs and n floors, and an unknown critical floor above which eggs break. A drop either breaks the egg, which is then gone, or doesn't, and you can reuse it. What's the fewest number of drops that guarantees finding the critical floor? With one egg you must go floor by floor: n drops. With unlimited eggs, binary search needs about log2(n). Everything in between is a DP, and the trick is to recur on the right question: not "how many drops for n floors?" but "how many floors can m drops cover?"
We'll go from simple to more technical:
- The pattern: covered[m][k] = covered[m - 1][k - 1] + covered[m - 1][k] + 1.
- A second flavor: two eggs, a closed form, and the drop schedule.
- Where worst-case planning with few spares shows up (stress tests, bisecting with costly probes).
- What breaks it: the slow direct DP, mixed-up sides, overflow, naive binary search.
The approach
Asking "fewest moves for (k eggs, n floors)" directly means trying every first floor to drop from - O(k * n^2). Invert it: with m moves and k eggs, how many floors can you always handle?
Java
int superEggDrop(int k, int n) {
int[][] covered = new int[n + 1][k + 1]; // covered[m][e] = most floors m moves and e eggs can handle
int m = 0;
while (covered[m][k] < n) {
m++;
for (int e = 1; e <= k; e++) {
covered[m][e] = covered[m - 1][e - 1] // it broke: the floors below, one egg fewer
+ covered[m - 1][e] // it survived: the floors above, same eggs
+ 1; // the floor just tested
}
}
return m;
}
Python
def super_egg_drop(k: int, n: int) -> int:
covered = [[0] * (k + 1) for _ in range(n + 1)] # covered[m][e] = most floors m moves and e eggs can handle
m = 0
while covered[m][k] < n:
m += 1
for e in range(1, k + 1):
covered[m][e] = (covered[m - 1][e - 1] # it broke: the floors below, one egg fewer
+ covered[m - 1][e] # it survived: the floors above, same eggs
+ 1) # the floor just tested
return m
Drop from the floor that leaves exactly covered[m - 1][e - 1] floors below it. If the egg breaks, those floors are handled with the remaining moves and eggs; if it survives, covered[m - 1][e] floors above are. The answer is the first m whose coverage reaches n - so the loop runs only as many times as the answer, which is small.
A second flavor: two eggs and a closed form
With two eggs, covered[m][1] = m (one egg: floor by floor), so covered[m][2] = covered[m - 1][2] + (m - 1) + 1 = 1 + 2 + ... + m = m(m + 1)/2. The answer for n floors is the smallest m with m(m + 1)/2 >= n:
Java
long covered = 0;
int moves = 0;
while (covered < n) { moves++; covered += moves; } // long: passes Integer.MAX_VALUE near n = 2^31
return moves;
Python
covered = moves = 0
while covered < n: # Python ints never overflow - no long needed
moves += 1
covered += moves
For 100 floors that's 14: drop the first egg at 14, then 27, 39, 50, ... (each gap one smaller, because each drop used up a move), and walk up with the second egg once the first breaks. For n = 2,147,483,647 the answer is 65,536 - and the running total passes the int range on the way, so it must be a long.
Where you'll see it
Destructive testing with limited samples (stress-testing prototypes, finding a load threshold with a fixed number of test articles) and "bisecting with a budget" in software - finding the release that introduced a regression when each failing test run is expensive or consumes a limited environment - are egg-drop problems. The inverted question ("what can this budget cover?") is a general trick for "minimum resources to guarantee an outcome".
Which tool for which job?
| You need | Use |
|---|---|
| Fewest drops for k eggs, n floors | the coverage DP, increasing m until it covers n |
| Two eggs | the smallest m with m(m + 1) / 2 ≥ n |
| Huge n (10^18) | binary search on m with covered = C(m, 1) + ... + C(m, k) |
| The actual drop schedule | gaps that shrink by one: 14, 27, 39, ... for 100 floors |
| Enough eggs (k ≥ log2(n + 1)) | binary search |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| The direct "min drops for (k, n)" DP | 1,001,000 steps where 57 suffice | the coverage DP |
| Mixing up the sides | wrong recurrence | a broken egg means below, with one egg fewer |
int totals in the closed form | overflow near n = 2^31 | long |
mid × (mid + 1) in a long binary search | 10^18 floors gives 123586651867261452 drops | cap mid before multiplying |
| Binary search with two eggs | a break at the midpoint leaves too few eggs | the shrinking-gap schedule |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why is covered[m][e] = covered[m - 1][e - 1] + covered[m - 1][e] + 1?
Show answer
Drop from a floor with exactly covered[m - 1][e - 1] floors below it. If it breaks, you have m - 1 moves and e - 1 eggs for those floors below; if it survives, m - 1 moves and e eggs for the floors above - covered[m - 1][e] of them. The floor you tested is the + 1.
2. With 2 eggs and 100 floors, how many drops are needed, and where does the first egg go?
Show answer
14, the smallest m with m(m + 1)/2 >= 100. The first egg goes at 14, then 27, 39, 50, 60, ... - each gap one smaller - so if it breaks, the second egg's floor-by-floor search plus the drops so far always totals at most 14.
3. With 1 egg, why can't you do better than n drops?
Show answer
If the only egg breaks, you learn nothing about the floors between the last safe drop and this one. So you can never skip a floor: you must test 1, 2, 3, ... in order, and the worst case is n drops.
Key takeaways
- Invert the question: with m moves and k eggs, how many floors can you always handle?
- covered[m][k] = covered[m - 1][k - 1] + covered[m - 1][k] + 1 - broke below, survived above, plus the tested floor.
- The answer is the first m whose coverage reaches n; the loop runs "answer" times.
- Two eggs: m(m + 1)/2 floors - use 64-bit math for large n.
- One egg: n drops; unlimited eggs: about log2(n + 1).