Egg Drop Problem, in depth: the min-max recurrence, binary-search speed-up, the moves reformulation, strategy reconstruction and failure-budget probing

Defining the problem precisely

Fix the model before writing code, because sloppy definitions cause most wrong answers. Let the floors be 1 to n and let the answer F be the lowest floor at which an egg breaks, or n + 1 if none does. That gives n + 1 possible answers. A drop from floor x either breaks the egg, which tells us F ≤ x and costs an egg, or it does not, which tells us F > x and keeps the egg. The outcome is monotone: if it breaks at x it breaks at every floor above x. That monotonicity is the whole reason the search is possible.

Two boundary cases anchor everything. With one egg you cannot risk skipping a floor, because if the egg breaks after a skip you can no longer tell which skipped floor was the threshold. So one egg needs n drops, walking up from floor 1. With unlimited eggs the problem is binary search, which needs ⌈log₂(n + 1)⌉ drops. Every other case lies between these two.

The classic recurrence

Let D(k, n) be the minimum worst-case drops with k eggs and n floors still in question. Drop at floor x of the current range. If the egg breaks, the threshold is in the x - 1 floors below with k - 1 eggs. If it survives, it is in the n - x floors above with k eggs. The adversary chooses the worse outcome and we choose the best x:

D(k, 0) = 0
D(1, n) = n
D(k, n) = 1 + min over x in 1..n of max( D(k-1, x-1), D(k, n-x) )

def egg_drop_naive(k, n):
    INF = float("inf")
    D = [[0] * (n + 1) for _ in range(k + 1)]
    for j in range(1, n + 1):
        D[1][j] = j
    for i in range(2, k + 1):
        for j in range(1, n + 1):
            best = INF
            for x in range(1, j + 1):
                best = min(best, 1 + max(D[i - 1][x - 1], D[i][j - x]))
            D[i][j] = best
    return D[k][n]

This is O(kn²) time and O(kn) space. It is correct and fine for n in the hundreds. For n = 10,000 and k = 4 it does about 150 million inner steps, which is too slow in Python. The table also only gives the number, not the strategy, and the strategy is what you actually use.

Binary search on the drop floor

Look at the two terms inside the max as functions of x. D(k-1, x-1) can only grow as x grows: more floors below means more work. D(k, n-x) can only shrink: fewer floors above. The max of a non-decreasing and a non-increasing function is smallest where they cross, so we can binary search for the crossing instead of scanning every x.

def egg_drop_bs(k, n):
    D = [[0] * (n + 1) for _ in range(k + 1)]
    for j in range(1, n + 1):
        D[1][j] = j
    for i in range(2, k + 1):
        for j in range(1, n + 1):
            lo, hi = 1, j
            while lo + 1 < hi:
                mid = (lo + hi) // 2
                broke, survived = D[i - 1][mid - 1], D[i][j - mid]
                if broke < survived:
                    lo = mid
                elif broke > survived:
                    hi = mid
                else:
                    lo = hi = mid
            D[i][j] = 1 + min(max(D[i - 1][x - 1], D[i][j - x]) for x in (lo, hi))
    return D[k][n]

That is O(kn log n). There is a further step to O(kn): the best x for (k, n) never decreases as n grows, so a pointer can move forward across a row instead of searching again. It works, but the reframing in the next section is simpler and much faster, so most practitioners skip straight to it.

Turning the question around: floors per drop

Turn the question around. Instead of asking how many drops n floors need, ask how many floors m drops can handle. Let f(m, k) be the largest number of floors for which m drops and k eggs always find the threshold. Make the first drop. If it breaks, the remaining m - 1 drops and k - 1 eggs must handle the floors below, so at most f(m-1, k-1) floors can sit below it. If it survives, m - 1 drops and k eggs handle the floors above, so f(m-1, k) floors can sit above. Add the floor we dropped from:

f(0, k) = 0,  f(m, 0) = 0
f(m, k) = f(m-1, k-1) + f(m-1, k) + 1
answer  = smallest m with f(m, k) >= n

def egg_drop_moves(k, n):
    if n == 0:
        return 0
    f = [0] * (k + 1)          # f[i] = floors coverable with m drops and i eggs
    m = 0
    while f[k] < n:
        m += 1
        for i in range(k, 0, -1):   # downward, so f[i-1] still holds the m-1 value
            f[i] = f[i] + f[i - 1] + 1
    return m

This runs in O(k · m) time and O(k) memory, where m is the answer. With many eggs m is about log₂ n, but with two eggs m grows like √(2n), so the loop alone is too slow for n = 10¹⁸. The loop direction is the one bug to watch: iterating upward would mix the m and m - 1 values. In fixed-width languages, also cap f at n, because the counts grow like binomial coefficients and overflow quickly.

The recurrence has a closed form, f(m, k) = C(m, 1) + C(m, 2) + ... + C(m, k). With k = 1 that is m, matching the one-egg walk. With k ≥ m it is 2^m - 1, which is binary search. The formula makes quick estimates easy. For 3 eggs and 100 floors: 8 drops cover 8 + 28 + 56 = 92 floors and 9 drops cover 9 + 36 + 84 = 129, so the answer is 9. Because f grows with m, we can also binary search m and evaluate the sum term by term, stopping once it reaches n. That is O(k log n) for any input:

def covers(m, k, n):                 # is C(m,1) + ... + C(m,k) >= n ?
    total, term = 0, 1
    for i in range(1, k + 1):
        term = term * (m - i + 1) // i   # C(m, i), exact
        total += term
        if total >= n or term == 0:
            break
    return total >= n

def egg_drop_fast(k, n):
    lo, hi = 0, n                    # n drops always suffice with one egg or more
    while lo < hi:
        mid = (lo + hi) // 2
        if covers(mid, k, n):
            hi = mid
        else:
            lo = mid + 1
    return lo

Worked example and strategy reconstruction

Two eggs and 100 floors is the classic interview case. f(m, 2) = m + m(m-1)/2 = m(m+1)/2. The smallest m with m(m+1)/2 ≥ 100 is 14, because 13 · 14 / 2 = 91 and 14 · 15 / 2 = 105. So 14 drops.

The strategy comes from the same reasoning. With 14 drops left, the first egg goes to floor 14. If it breaks, the second egg walks floors 1 to 13: at most 13 more drops, 14 in total. If it survives, 13 drops remain, so the next drop goes 13 floors higher, to 27. Then 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100. Every branch costs at most 14. A naive plan that jumps 10 floors at a time costs up to 19 drops: 10 drops of the first egg and 9 of the second.

The same rule works for any k. With m drops left and k eggs, drop at low + f(m-1, k-1) + 1, where low is the highest floor known to be safe. Here is a strategy runner that can be checked against every possible threshold:

from functools import lru_cache

@lru_cache(None)
def cover(m, k):
    if m == 0 or k == 0:
        return 0
    return cover(m - 1, k - 1) + cover(m - 1, k) + 1

def find_threshold(k, n, breaks):      # breaks(x) -> bool, monotone in x
    m = egg_drop_moves(k, n)
    low, high, drops = 0, n + 1, 0     # threshold is in (low, high]
    while high - low > 1:
        x = min(low + cover(m - 1, k - 1) + 1, high - 1)
        drops += 1; m -= 1
        if breaks(x):
            high, k = x, k - 1
        else:
            low = x
    return high, drops                  # high == n + 1 means it never breaks

for t in range(1, 102):
    found, used = find_threshold(2, 100, lambda x: x >= t)
    assert found == t and used <= 14

The final loop is the test that matters. It runs the strategy against every possible threshold, including "never breaks", and asserts both correctness and the worst-case bound. Exhaustive checks like this are cheap for small n and catch the off-by-one errors that hand-written proofs miss.

Where the model applies

The puzzle is a model for a monotone search where a failed probe consumes a scarce resource. Examples from systems work:

• Finding the largest batch size before out-of-memory on a shared GPU node where each OOM crash costs a pod restart and a scheduler queue wait. You can afford a few crashes, not dozens.
• Load testing a production-like service where each overload trips a circuit breaker with a long cooldown, or pages a person.
• Bisecting with destructive tests, such as hardware stress runs that may damage a sample, or migrations that need a restore after failure.

Map the parameters: k is the failure budget plus one, and n is the number of candidate settings, for example batch sizes in steps of 8. Ask the operator for k first. If they can afford ⌈log₂(n + 1)⌉ failures, plain binary search is optimal and you are done. If they can afford one, you must walk upward linearly. In between, the f(m, k) schedule gives the least probes. Two cautions for the real world. Many thresholds are not cleanly monotone: OOM depends on fragmentation and sequence length as well as batch size. And a probe can be noisy, which the puzzle assumes away. Repeat probes near the boundary, or back off by a safety margin, before trusting the answer.

Bugs that break solutions

Trade-offs and related problems

The naive O(kn²) table is the easiest to derive and explain, and it is the version to start from in an interview before improving it. The binary-search version keeps the same state, so it is a safe upgrade. The moves formulation is the fastest and smallest, but its correctness argument is less obvious, so pair it with the exhaustive strategy test above. For systems work, the difference between O(kn) and O(k log n) rarely matters, because n is small. What matters is the drop schedule and the monotonicity assumption.

If this is your first constrained DP, read dynamic programming in depth for state design, then compare the min-of-max structure here with the min-of-sum in coin change and the capacity dimension in knapsack.

What to do next

1. Implement egg_drop_naive and egg_drop_moves and check they agree for all k ≤ 4 and n ≤ 200.
2. Run the exhaustive find_threshold test for k = 2, 3 and n = 100, 1000.
3. Compute the 3-egg, 100-floor schedule by hand from f(m, k) and compare it with the code.
4. Solve the problem with n = 10⁹ and k = 2 using the closed form, without a loop over floors.
5. Pick one capacity probe in your systems, such as batch size or concurrency, and write down its failure budget, n and the schedule.
6. Add a safety margin and a repeat-near-boundary rule before adopting a threshold found by destructive probes.