Egg Dropping

Problem. You have $k$ identical eggs and a building with $n$ floors. There is a threshold floor $f$: an egg dropped from floor $f$ or below survives; above $f$ it breaks. A broken egg cannot be reused. In the worst case, what is the minimum number of drops needed to determine $f$ exactly?

The naive DP — $O(k{n}^2)$

$dp[k][n]=1+{\min }_{1\le x\le n}\max (dp[k-1][x-1],dp[k][n-x]).$

Dropping from floor $x$: if the egg breaks, $k-1$ eggs remain and $x-1$ floors below; if it survives, $k$ eggs and $n-x$ floors above.

int eggDrop(int k, int n) {
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) dp[1][i] = i;              // one egg: linear scan
    for (int e = 2; e <= k; e++)
        for (int f = 1; f <= n; f++) {
            dp[e][f] = INT_MAX;
            for (int x = 1; x <= f; x++)
                dp[e][f] = min(dp[e][f], 1 + max(dp[e-1][x-1], dp[e][f-x]));
        }
    return dp[k][n];
}

The inverted DP — $O(kn)$, and it is the better formulation

Flip the question: with $e$ eggs and $t$ drops, how many floors can I distinguish?

$f[e][t]=f[e-1][t-1]+f[e][t-1]+1.$

The first term counts the floors below (egg broke), the second the floors above (egg survived), and the $+1$ is the floor tested. Increase $t$ until $f[k][t]\ge n$.

int eggDropFast(int k, int n) {
    vector<int> f(k + 1, 0);
    int t = 0;
    while (f[k] < n) {
        t++;
        for (int e = k; e >= 1; e--) f[e] = f[e] + f[e-1] + 1;   // in place, downward
    }
    return t;
}

$O(k\cdot t)$ with $t=O(\log n)$ for $k\ge \log n$ — effectively instant.

The closed form

$f[k][t]={\sum }_{i=1}^k\left(\genfrac{}{}{0ex}{}{t}{i}\right),$

so the answer is the smallest $t$ with ${\sum }_{i=1}^k\left(\genfrac{}{}{0ex}{}{t}{i}\right)\ge n$.

Why: a strategy is a decision tree of depth $t$ in which each root-to-leaf path uses at most $k$ “break” branches. The number of such paths is exactly the number of binary strings of length $t$ with at most $k$ ones.

Special cases

$k$	Answer
1	$n$ (linear scan from the bottom)
2	smallest $t$ with $\frac{t(t+1)}{2}\ge n$, i.e. $\approx \sqrt{2n}$
$\ge {\log }_{2}n$	$\lceil {\log }_2(n+1)\rceil$ — plain binary search

The two-egg case is the famous one: for $n=100$ the answer is 14, achieved by first dropping from floor 14, then 27, then 39, … (decreasing gaps), not from floor 50.

The decreasing-gap structure is the point: each failed drop costs one egg and one attempt, so the next interval must be one shorter.

The technique it teaches

When a DP’s answer range is small but its state space is large, invert it — make the answer an index and the state a value.

Here, “minimum drops for $n$ floors” ($O(n)$ states, $O(n)$ transitions) becomes “maximum floors with $t$ drops” ($O(\log n)$ values of $t$, $O(1)$ transitions). The same inversion turns the $O(nW)$ knapsack into $O(n\sum v)$ when the values are small, and is worth checking on any DP with an awkward dimension.

Variants

• Minimise the expected drops (rather than the worst case) — a different DP, over probability distributions.
• Eggs of different fragility — each has its own threshold.
• $k$ eggs, exactly $t$ drops, count the strategies — the binomial sum above.
• Adversarial floors — the standard version already assumes an adversary chooses $f$.

See also: Introduction to DP · Binary Search · Combinatorics