Why this matters
The egg drop puzzle is a classic test of dynamic programming. The question looks like a physics riddle, but the solution is a table, a recurrence and a loop order, the same tools used in the knapsack and coin change lessons. It also shows a useful habit. Sometimes the table is easier to build when its rows count something other than the obvious thing. Here the rows count moves (drops), not floors.
The puzzle gives you a tower with n floors and k eggs. You want to know the highest floor from which an egg survives a drop. Call that the critical floor. An egg that survives can be used again. An egg that breaks is gone. You want a plan that finds the critical floor in the fewest drops for the worst possible answer. This is the same kind of question as "what is the worst case for this strategy", which comes up often when a program has to plan for bad inputs.
This lesson has three parts. The first builds a table indexed by floors and tries every floor for the first drop. It is correct but slow. The second flips the table so that it counts moves, and this is much faster for large inputs. The third uses a closed formula from the second part to replace the loop with a binary search (a search that halves the range of possible answers at each step). Each part gives the same answers, and the program checks that.
The problem in small steps
Start with one egg and three floors. Floors are numbered 1, 2 and 3. The egg breaks above the critical floor. If the egg survives a drop from floor 2, the critical floor is at least 2. If it breaks, the critical floor is 1 or lower.
With one egg, there is only one safe method. Drop from floor 1. If it survives, drop from floor 2. If that survives, drop from floor 3. The egg has to be dropped from every floor from the bottom up, because breaking it removes the only way to continue. So with one egg and three floors, the worst case is 3 drops.
Now add a second egg. With two eggs and three floors, drop the first egg from floor 2. If it breaks, the critical floor is 1 or 0. Use the second egg from floor 1 to decide. That is at most 2 drops in total. If the first egg survives the drop from floor 2, the critical floor is 2 or 3, and one drop from floor 3 settles it. Either way the worst case is 2 drops. The second egg makes the search shorter.
The answer depends on both numbers. More eggs make the search shorter, and more floors make it longer. The rest of this lesson turns that idea into a table.
Part 1: try every floor for the first drop
Let fewest[k][n] mean the fewest drops that always find the critical floor, when there are k eggs and n floors. The critical floor can be any of the values 0 to n. The value 0 means an egg breaks even when dropped from floor 1.
Three starting values are easy to see:
- With no floors, nothing needs to be found, so
fewest[k][0]is 0. - With one egg, the method from the first section is forced, so
fewest[1][n]isn. - With more eggs, we try every floor
xfor the first drop, from 1 ton.
For a drop from floor x, there are two outcomes. If the egg breaks, the critical floor is below x, so we have x - 1 floors and k - 1 eggs left. If the egg survives, the critical floor is at or above x, so we have n - x floors above and k eggs left. The worst of the two outcomes decides the cost of that drop. We pick the floor x that makes this worst cost smallest:
fewest[k][n] = 1 + min over x from 1 to n of max(fewest[k - 1][x - 1], fewest[k][n - x])The 1 is for the drop itself. The max takes the worse of the two outcomes, because the plan has to work even in the worst case. The min picks the best first floor.
A small table
Here are the values for one egg and for two eggs, for n from 0 to 10. They were computed by the same recurrence in a Python check:
floors n: 0 1 2 3 4 5 6 7 8 9 10
1 egg: 0 1 2 3 4 5 6 7 8 9 10
2 eggs: 0 1 2 2 3 3 3 4 4 4 4Look at the row for two eggs at n equal to 10. The answer is 4. Here is one plan that reaches that count. Drop the first egg from floor 4. If it breaks, the critical floor is 0 to 3, and one egg must try floors 1, 2 and 3 in turn. That is 1 drop plus 3 drops, which is 4 in the worst case. If it survives, 6 floors remain, from 5 to 10, with two eggs. The next best drop is from floor 7, and so on.
The program
Here is the first method as code. The program reads the number of eggs and floors, then prints the answer from each of the three methods. The first line comes from this function.
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <vector>
// Method 1: try every floor. fewest[k][n] is the fewest drops that always
// find the critical floor with k eggs and n floors. O(eggs * floors^2) time.
int fewest_drops_by_floor(int eggs, int floors) {
constexpr int INF = std::numeric_limits<int>::max() / 2;
std::vector<std::vector<int>> fewest(eggs + 1, std::vector<int>(floors + 1, INF));
for (int k = 0; k <= eggs; ++k) fewest[k][0] = 0; // no floors, no drop needed
for (int n = 1; n <= floors; ++n) fewest[1][n] = n; // one egg: go up one floor at a time
for (int k = 2; k <= eggs; ++k) {
for (int n = 1; n <= floors; ++n) {
for (int x = 1; x <= n; ++x) { // drop the egg from floor x
int worst = std::max(fewest[k - 1][x - 1], fewest[k][n - x]);
fewest[k][n] = std::min(fewest[k][n], 1 + worst);
}
}
}
return fewest[eggs][floors];
}
// Method 2: a table indexed by moves. reach[k] holds the number of floors
// that k eggs can handle with the moves used so far. Time is O(eggs * answer).
long long fewest_drops_by_moves(int eggs, long long floors) {
if (floors == 0) return 0;
std::vector<long long> reach(eggs + 1, 0);
long long moves = 0;
while (reach[eggs] < floors) {
++moves;
// Go downwards so reach[k - 1] still holds the value from the last move.
for (int k = eggs; k >= 1; --k) {
reach[k] = reach[k - 1] + reach[k] + 1;
}
}
return moves;
}
// Method 3: binary search on the number of moves. With m moves and k eggs,
// the floors covered are C(m,1) + C(m,2) + ... + C(m,k).
// True when `moves` drops can handle `floors` floors with `eggs` eggs.
bool enough(int eggs, long long moves, long long floors) {
__int128 term = 1; // C(moves, 0)
__int128 total = 0;
for (long long i = 1; i <= eggs && i <= moves; ++i) {
// term is still below floors here, so this product fits in 128 bits.
term = term * (moves - i + 1) / i; // C(moves, i)
total += term;
if (total >= floors) return true;
}
return total >= floors;
}
// Needs at least one egg.
long long fewest_drops_fast(int eggs, long long floors) {
if (floors == 0) return 0;
long long lo = 1, hi = floors; // `floors` drops always work with one egg
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (enough(eggs, mid, floors)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
int main(int argc, char* argv[]) {
if (argc != 3) {
std::cerr << "usage: egg_drops EGGS FLOORS\n";
return EXIT_FAILURE;
}
int eggs = std::atoi(argv[1]);
long long floors = std::atoll(argv[2]);
if (eggs < 1) {
std::cerr << "need at least one egg\n";
return EXIT_FAILURE;
}
std::cout << "by floor: " << fewest_drops_by_floor(eggs, static_cast<int>(floors)) << '\n';
std::cout << "by moves: " << fewest_drops_by_moves(eggs, floors) << '\n';
std::cout << "fast: " << fewest_drops_fast(eggs, floors) << '\n';
}Compile it with the usual flags, then run the two-eggs example with 10 floors:
$ g++ -std=c++20 -Wall -o egg_drops egg_drops.cpp
$ ./egg_drops 2 10
by floor: 4
by moves: 4
fast: 4All three lines say 4. The first method is correct, and it is the reference for the other two. Its cost is about eggs * floors * floors steps. For 10 floors that is about 100 steps for each egg. For 1,000 floors it is about a million steps for each egg. For a quintillion floors it cannot run at all.
Part 2: a table indexed by moves
The first method asks "how many floors can I handle?" for each floor count. The second method turns the question around. It fixes the number of moves and asks "how many floors can I handle with this many moves?"
Let reach[k][m] be the largest number of floors that k eggs can handle with m moves. A move is one drop. With no moves, no floor can be tested, so reach[k][0] is 0. With no eggs, the egg cannot be dropped at all, so reach[0][m] is 0. With one egg and m moves, we can test m floors from the bottom up, so reach[1][m] is m.
For the rest, consider the first drop with k eggs and m moves left. Drop from some floor. There are two outcomes, as before:
- The egg breaks. Now
k - 1eggs andm - 1moves remain, so the floors below the drop must fit inreach[k - 1][m - 1]. - The egg survives. Now
keggs andm - 1moves remain, so the floors above the drop must fit inreach[k][m - 1].
The drop floor itself is one more floor. So the total number of floors that can be handled is the sum of the two parts and the floor itself:
reach[k][m] = reach[k - 1][m - 1] + reach[k][m - 1] + 1This recurrence has no minimum over floors, because the table is built from the number of moves instead. Each cell depends on two cells in the row above it, which is the same shape as the earlier DP tables.
The table
For 1 to 3 eggs and 0 to 6 moves, the table looks like this. It was computed by the recurrence in a Python check.
moves m: 0 1 2 3 4 5 6
1 egg: 0 1 2 3 4 5 6
2 eggs: 0 1 3 6 10 15 21
3 eggs: 0 1 3 7 14 25 41Read the row for 2 eggs and 4 moves. The value is 10, so 4 moves handle up to 10 floors with 2 eggs. That is why the answer for 2 eggs and 10 floors is 4. The answer is the smallest number of moves m with reach[k][m] at least n.
For 3 eggs and 4 moves, the value is 14. So 3 eggs and 4 moves can handle 14 floors. The answer for 3 eggs and 14 floors is therefore at most 4, and 3 moves are not enough, because reach[3][3] is 7.
The program
The second method keeps only one row, not the whole table. It updates reach[k] for each move, and it stops once the top egg count covers the floors.
The loop over eggs runs downwards for the same reason as the knapsack loop in the earlier lesson. The value reach[k - 1] must still be the value from the previous move when reach[k] is updated. If the loop went upwards, reach[k - 1] would already hold the new value for this move, and the result would be wrong. The section on mistakes shows that wrong output.
The second method is in the file above. Its answers match the first method for every case checked, as the test section below shows.
The cost is about eggs * answer steps. The answer grows slowly when there are many eggs, but it grows fast when there are few. With one egg it is floors, because the only plan is to test every floor. With two eggs it is about the square root of twice the number of floors. For 1 billion floors and two eggs, the answer is about 44,721 drops, so the loop runs 89,000 times or so. That is fast. For 1 billion floors and one egg, the loop runs a billion times, which is slow.
Part 3: a closed form and a binary search
The table has a pattern. For 2 eggs, the values in the table are 1, 3, 6, 10, 15, 21. These are the triangular numbers, and each one is C(m,1) + C(m,2) for m moves. For 3 eggs, the values are C(m,1) + C(m,2) + C(m,3). Check the last column for 3 eggs and 6 moves: 6 + 15 + 20 = 41, which matches the table.
In general, with k eggs and m moves:
reach[k][m] = C(m,1) + C(m,2) + ... + C(m,k)Here C(m,i) is the number of ways to choose i items from m. We do not need the table to compute this. The formula only depends on k and m.
The formula is useful because reach[k][m] is increasing in m. More moves never cover fewer floors. So the question "what is the fewest moves for n floors" has a monotone answer. We can binary search on m. For each candidate m, we check with the formula whether it reaches n floors. That check takes k steps, because it adds k binomial terms. So the total time is about k * log(n).
Computing the binomials safely
The binomial C(m,i) can be computed one step at a time:
C(m,i) = C(m,i-1) * (m - i + 1) / iEach division is exact, because the result is always a whole number. The intermediate product can be very large when m is around 10 to the power 18. The program stores the terms in __int128, a 128-bit integer type that some compilers provide. It stops as soon as the running total reaches n. Before that point every term is below n, so the product is at most about n times m, which fits in 128 bits.
__int128 is not part of the C++ standard. The GCC and Clang compilers provide it on 64-bit systems. Another way is to use a library for big integers. The idea is the same.
The program
The third method is in the file above, as fewest_drops_fast and enough. The main function prints its answer as the third line.
With the same input as before, the output is:
$ ./egg_drops 2 10
by floor: 4
by moves: 4
fast: 4Now try a bigger input, where the table method would be slow:
$ ./egg_drops 3 100
by floor: 9
by moves: 9
fast: 9The first two methods run here because 100 is small. For very large floor counts only the third method finishes in a useful time, and it does so in well under a second. The test below runs all three methods on 3,010 cases and reports whether they agree.
Test results
The test program includes the same file, renames its main so it does not clash, and compares the three functions for eggs from 1 to 10 and floors from 0 to 300. It reports every case where they disagree.
checked 3010 pairs, mismatches 0
k=2 n=0 -> 0
k=2 n=1 -> 1
k=2 n=2 -> 2
k=2 n=10 -> 4
k=2 n=100 -> 14
k=1 n=10 -> 10
k=3 n=100 -> by floor 9, fast 9
k=10 n=1000000000000000000 -> 290
k=2 n=1000000000000000000 -> 1414213562
k=1 n=1000000000000000000 -> 1000000000000000000The last three lines show the fast method on very large inputs. With 10 eggs and a quintillion floors the answer is 290. With 2 eggs it is 1,414,213,562, which is about the square root of twice the number of floors. With 1 egg it is the number of floors itself, because the only plan is a straight walk up.
Larger examples
Two eggs and 100 floors
The answer is 14. The first method does about 10,000 steps for each egg, and the moves table about 28 steps. The binary search needs about 7 steps, and each step uses at most two binomial terms. All three give 14.
Three eggs and 100 floors
The answer is 9, as the run above shows. The value 9 satisfies reach[3][9] = 9 + 36 + 84 = 129, which is at least 100, and reach[3][8] = 8 + 28 + 56 = 92, which is less than 100. So 9 is the smallest move count that works.
Ten eggs and a quintillion floors
This is the largest case. The answer is 290. The moves table would also finish quickly here, in about 2,900 steps, because the answer is 290. The closed form needs about 10 binomial terms for each of about 60 binary search steps. The main point is that the answer is small. Ten eggs can handle a huge tower in a few hundred drops, because each new egg multiplies the reach of the plan.
Common mistakes
Off-by-one in the floor count
The most common mistake is to add one to the floor count. Floors are numbered 1 to n, and the critical floor can be 0 to n, which is n + 1 cases. The formulas already count this, so the input is n, not n + 1. A program that passes n + 1 gets 11 instead of 10 for 1 egg. Check your code against the table above: 1 egg and 10 floors must give 10, and 2 eggs and 10 floors must give 4.
Zero floors
With no floors there is nothing to find, so the answer is 0. Without the check if (floors == 0) return 0;, the binary search starts with lo = 1 and hi = 0, and it returns 1 for an empty tower. The check prevents that.
Zero eggs
With no eggs and at least one floor, the puzzle cannot be solved. The fast method does not know this. Its check enough never finds enough floors, so the binary search keeps going up and returns floors. The output is a number, and it looks plausible. Here is what the function prints when it is called with zero eggs and five floors, without the guard in main:
0 eggs, 5 floors (no guard): 5The answer 5 is wrong, because five floors cannot be searched with no eggs. The program prevents this by checking eggs < 1 in main before it calls any function.
Looping upwards in the moves table
The moves table reads the old value of reach[k - 1]. If the loop goes from k = 1 up to eggs, the value of reach[k - 1] is the new value for this move, and the answer is wrong. This small program has that mistake:
// Same as fewest_drops_by_moves, but the loop goes upwards (wrong).
for (int k = 1; k <= eggs; ++k) {
reach[k] = reach[k - 1] + reach[k] + 1;
}Its output for 2 eggs and 5 floors is:
upward, 2 eggs, 5 floors: 2The correct answer is 3. The table says 2 eggs and 2 moves cover up to 3 floors, which is less than 5, so 2 moves are not enough. The upward loop uses the new reach[1] when it updates reach[2], which lets this one move count twice.
Overflow in the binomial product
The product term * (moves - i + 1) can be very large. With a long long instead of __int128, the product overflows when the binary search tests a large number of moves. For 2 eggs and a quintillion floors, the first midpoint is 500,000,000,000,000,000, and the product for that midpoint is already too large for a long long. This program does the same computation with long long:
long long term = 1;
long long total = 0;
for (long long i = 1; i <= eggs && i <= moves; ++i) {
term = term * (moves - i + 1) / i;
total += term;
if (total >= floors) return true;
}With -fsanitize=undefined, the program reports the overflow the first time it happens:
egg_mistakes.cpp:25:21: runtime error: signed integer overflow: 500000000000000000 * 499999999999999999 cannot be represented in type 'long long int'
long long search, 2 eggs, 1e18 floors: 123586651867261452The printed answer, 123,586,651,867,261,452, is wrong. The correct answer is 1,414,213,562. Use __int128 for the product, or stop the check before the product can grow past the limit.
Using the wrong number of drops for the first step
Some people try to find the first drop floor by guessing. The table gives it directly. For k eggs and n floors, the first drop is from floor reach[k - 1][m - 1] + 1, where m is the answer. For 2 eggs and 10 floors, m is 4, so the first drop is from reach[1][3] + 1 = 3 + 1 = 4.
Practice
Exercise 1. One egg and 7 floors. How many drops are needed in the worst case?
Show the answer
Seven. With one egg, the only safe plan is to drop from floor 1, then floor 2, and so on. The worst case is that the egg survives every drop from floor 1 to floor 7, so all seven drops are needed. The table value reach[1][m] = m gives the same answer: 7 moves cover 7 floors.
Exercise 2. Two eggs and 6 floors. What is the answer?
Show the answer
Three. The table row for 2 eggs has reach[2][3] = 6, and reach[2][2] = 3 is less than 6. So three drops are needed. A plan: drop from floor 3. If it breaks, floors 1 and 2 remain, and the last egg tests floor 1, then floor 2, which is two drops. If it survives, floors 4 to 6 remain, so drop from floor 5. If that breaks, test floor 4. If it survives, test floor 6. The worst case is 3 drops.
Exercise 3. Three eggs and 4 moves. How many floors can the plan handle?
Show the answer
Fourteen. The formula gives C(4,1) + C(4,2) + C(4,3) = 4 + 6 + 4 = 14. The table value reach[3][4] is also 14.
Exercise 4. With two eggs and 10 floors, from which floor should the first drop be made?
Show the answer
Floor 4. The answer is 4 moves, so the first drop is from reach[1][3] + 1 = 3 + 1 = 4. If the egg breaks, the three floors below it are tested with the last egg. If it survives, the six floors above it are handled with two eggs and three moves, because reach[2][3] = 6.
Exercise 5. Explain in one or two sentences why fewest_drops_by_moves loops over the eggs downwards.
Show the answer
When reach[k] is updated, the formula needs the old value of reach[k - 1], which is the value from the previous move. Going downwards updates reach[k] before reach[k - 1], so the old value is still in place when it is read.
Summary
- Egg drop asks for the fewest drops that always find the critical floor. The worst case decides the cost of each plan.
- A table indexed by floors and first drops is correct but grows with the square of the number of floors.
- A table indexed by moves, with
reach[k][m] = reach[k - 1][m - 1] + reach[k][m - 1] + 1, is much faster for large inputs. - The moves table has a closed form,
C(m,1) + ... + C(m,k), which lets a binary search find the answer in aboutktimeslog(n)steps. - In the moves table, update the eggs from the highest count down to 1, and keep the binomial products in a type large enough for the largest input.