Egg Drop Puzzle DP, in depth: the monotone optimum, the two-egg closed form, lower bounds and an overflow-safe solver

The state and the recurrence

Let D(k, n) be the minimum worst-case drops with k eggs and n candidate floors still in play. Only the count of floors matters, not where they are, because the problem is translation invariant: floors 41 to 60 behave exactly like floors 1 to 20. That is the observation that makes the state two-dimensional.

If you drop from the x-th remaining floor, two things can happen. The egg breaks, leaving k-1 eggs and the x-1 floors below. Or it survives, leaving k eggs and the n-x floors above. You do not choose the outcome, so you pay for the worse one, and you choose x to make that worst case as small as possible:

D(k, 0) = 0                     # nothing left to decide
D(1, n) = n                     # one egg: walk up floor by floor, no choice
D(k, n) = 1 + min over x in 1..n of max( D(k-1, x-1), D(k, n-x) )

There are n+1 possible answers (threshold at floor 1, ..., n, or never), not n; most off-by-one bugs start there.

A ladder of solutions

Every fast solution is the same recurrence with less wasted work. The table lists the rungs and the fact each one depends on. The k-by-m column refers to the dual formulation: count how many floors m drops and k eggs can decide, then search for the smallest sufficient m.

Up to a few thousand floors any rung is instant. At a million floors use the O(kn) table if you want the strategy; beyond that only the drops-count view scales.

Why the largest optimal first drop only moves right

For a fixed (k, n), the break branch D(k-1, x-1) is non-decreasing in x, and the survive branch D(k, n-x) is non-increasing in x. The maximum of a rising and a falling function is smallest where they cross, which is why binary search on x works. The stronger fact is about how the crossing moves when n increases by one: the survive curve shifts up or stays put at every x, so the crossing can only move right.

One subtlety, checked by brute force for up to 5 eggs and 300 floors: the optimum is often a plateau rather than a point. For 2 eggs and 100 floors, every first drop from floor 9 to floor 14 achieves 14 drops. The largest optimal x never decreases as n grows, but the smallest optimal x does go backwards at some n. A pointer argument must therefore track the right end of the plateau, which is exactly what advancing while the next floor is no worse does:

def egg_drop_monotone(k, n):
    dp = [list(range(n + 1))]                 # one egg: dp[j] = j
    for e in range(2, k + 1):
        prev, cur = dp[-1], [0] * (n + 1)
        x = 1                                 # pointer survives across j
        for j in range(1, n + 1):
            while x < j and max(prev[x], cur[j - x - 1]) <= max(prev[x - 1], cur[j - x]):
                x += 1                        # step right while it is no worse
            cur[j] = 1 + max(prev[x - 1], cur[j - x])
        dp.append(cur)
    return dp[-1][n]

The pointer moves at most n times per row, so the table costs O(kn). It matches brute force for k up to 5 and n up to 300.

Two eggs in closed form

With two eggs the structure is simple enough to solve by hand. With m drops in hand, the first drop can go no higher than floor m, because if it breaks you must walk floors 1 to m-1 one at a time with the last egg, using your remaining m-1 drops. If it survives you have m-1 drops and two eggs again, so the next jump can be at most m-1 floors, then m-2, and so on. The total coverage is m + (m-1) + ... + 1 = m(m+1)/2.

So two eggs with m drops decide m(m+1)/2 floors, and the answer for n floors is the smallest m with m(m+1)/2 at least n. For n = 100: 13 x 14 / 2 = 91 is too small and 14 x 15 / 2 = 105 is enough, so the answer is 14. The plan drops at floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and finally 100, each gap one smaller than the last. Breaking at 14 costs 1 + 13 linear drops; breaking at 27 costs 2 + 12; the worst case is 14 everywhere, which is what balanced means.

import math

def two_eggs(n):
    m = (math.isqrt(8 * n + 1) - 1) // 2     # largest m with m(m+1)/2 <= n
    while m * (m + 1) // 2 < n:              # round up when not exact
        m += 1
    return m

Use math.isqrt, not floating point: near 10^18 a double rounds the root and the answer drifts by one.

The lower bound and when extra eggs stop helping

Each drop has two outcomes, so d drops can distinguish at most 2^d situations. There are n+1 possible thresholds, so any strategy needs at least ceil(log2(n+1)) drops whatever the egg count. With unlimited eggs you meet that bound by plain binary search, which is why the problem is only interesting when eggs are scarce.

So if k is at least ceil(log2(n+1)), the answer is exactly that ceiling and no DP is needed. For 10^18 floors the ceiling is 60; the solver below returns 60 for 64 eggs. Every answer sits between ceil(log2(n+1)) and n, and both bounds make good test assertions.

An overflow-safe solver for huge buildings

For huge n, flip the question. F(m, k) is the number of floors that m drops and k eggs can decide. The first drop splits the building into what the broken branch can handle, F(m-1, k-1), the floor itself, and what the surviving branch can handle, F(m-1, k). Solving that recurrence gives F(m, k) = C(m,1) + C(m,2) + ... + C(m,k), derived in detail in the companion article. What matters here is computing it safely.

The sum grows explosively, so a naive implementation overflows 64-bit integers long before it reaches an interesting m. Cap the running total at n and stop as soon as you reach it. Then binary search the smallest m with F(m, k) at least n. Each probe costs O(k), and there are O(log n) probes:

def floors_covered(m, k, cap):
    total, term = 0, 1
    for i in range(1, k + 1):
        term = term * (m - i + 1) // i      # C(m, i) from C(m, i-1), exact
        total += term
        if total >= cap or term == 0:       # enough, or i has passed m
            break
    return min(total, cap)

def min_drops(k, n):
    if n == 0:
        return 0
    if k == 1:
        return n
    lo, hi = 1, n
    while lo < hi:
        mid = (lo + hi) // 2
        if floors_covered(mid, k, n) >= n:
            hi = mid
        else:
            lo = mid + 1
    return lo

print(min_drops(2, 100), min_drops(3, 100), min_drops(10, 10**18), min_drops(64, 10**18))
# 14 9 290 60

In Python the cap is about speed; in C++ or Java it is about correctness, so use 128-bit terms or check before multiplying. Multiply before dividing: term * (m - i + 1) // i is exact, dividing first truncates.

Worked example: 3 eggs, 100 floors

Take 3 eggs and 100 floors. Coverage with three eggs is C(m,1) + C(m,2) + C(m,3). At m = 8 that is 8 + 28 + 56 = 92, too few. At m = 9 it is 9 + 36 + 84 = 129, enough. So the answer is 9.

The plan falls out of the same numbers. With 9 drops, the first drop should leave the broken branch exactly what 2 eggs and 8 drops can handle, which is 8 + 28 = 36 floors. So drop from floor 37. If it breaks, floors 1 to 36 remain with 2 eggs and 8 drops, and 2-egg coverage at 8 drops is exactly 36. If it survives, 63 floors remain with 3 eggs and 8 drops, and coverage there is 92, comfortably enough. Brute force confirms that every first drop from 8 to 37 achieves 9; floor 37 is the right end of the plateau, the choice that keeps the monotone pointer valid.

Testing against brute force

Every rung above is an optimisation of the plain recurrence, so the plain recurrence is the oracle. A memoised brute force is short enough to trust by reading, and checking every fast solver against it on a grid of small inputs catches nearly every bug:

from functools import lru_cache
import math

@lru_cache(maxsize=None)
def brute(k, n):
    if n == 0:
        return 0
    if k == 1:
        return n
    return 1 + min(max(brute(k - 1, x - 1), brute(k, n - x)) for x in range(1, n + 1))

for k in range(1, 6):
    for n in range(0, 301):
        b = brute(k, n)
        assert egg_drop_monotone(k, n) == b
        assert min_drops(k, n) == b
        assert math.ceil(math.log2(n + 1)) <= b <= n
for n in range(0, 5000):
    assert two_eggs(n) == min_drops(2, n)

Raise the recursion limit, and keep n = 0 and k = 1 in the grid; refactors break those first.

Where the model applies, and where it breaks

The puzzle models any monotone threshold search where a failed probe consumes something scarce: the largest batch size before a GPU runs out of memory when each OOM kills a worker you can restart only a few times, or the request rate at which a service starts shedding load when each overload burns error budget.

The eggs are the failure budget and the drops are the probes. The model holds only when outcomes are monotone and deterministic; memory pressure and load thresholds drift, so add repeated trials or a margin.

Failure modes

• Counting n outcomes instead of n+1. The never-breaks case is a real outcome. Forget it and lower bounds and the two-egg formula both come out one off on some inputs.
• Tracking the wrong end of the plateau. The smallest optimal first drop is not monotone in n. Proofs or pointer code that assume it is can be wrong even when small tests pass.
• Overflow in the binomial sum. Without the cap, 64-bit code silently wraps and the binary search converges to garbage.
• Floating point square roots. The two-egg closed form drifts by one at large n.
• Using the model where outcomes are not monotone. The arithmetic is still exact, but the answer no longer means anything.

Trade-offs

The O(kn) table costs memory proportional to kn but hands you the whole strategy, including the plateau of acceptable first drops, which you need if probes have different costs. The binomial solver uses constant memory and answers any n, but it only gives the count; you rebuild the plan step by step from coverage numbers, as in the worked example. The closed form is fastest and only works for two eggs. For teaching and testing, keep the brute force forever.

The monotone-optimum trick is a cousin of the argument behind fast interval DPs such as matrix chain; the drops-count move generalises too: when the answer is small and the input huge, index by the answer.

What to do next

1. Implement the brute force and the monotone pointer, and assert they agree for k up to 5 and n up to 300.
2. Derive the two-egg plan for n = 100 by hand and check it against the coverage formula.
3. Implement the capped binomial solver in a fixed-width language and test it at n = 10^18.
4. Add the log2(n+1) and n bounds as assertions in your tests.
5. Write down one probing problem at work where failures are rationed, and check whether its outcome is truly monotone before applying the model.
6. Read the companion egg drop article for the binomial derivation, then the DP introduction and probability DP for the next state designs.