Egg Dropping Problem

The problem, simply

You have n eggs and a building with k floors. There is some floor where eggs start to break: an egg dropped from below it survives, and from it or above it breaks. It might even be that no floor breaks the egg.

An egg that survives can be dropped again. A broken egg is gone. Find the smallest number of drops that is always enough to find that floor, even with the worst luck.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every floor x for the first drop. Two things can happen:

• The egg breaks. The answer is below x: x - 1 floors left, n - 1 eggs.
• The egg survives. The answer is above x: k - x floors left, n eggs.

We must be ready for the worse of the two, so take the max. Then pick the floor x that makes this worst case smallest, so take the min over x. Add 1 for the drop itself.

1. k == 0 or k == 1: return k. One egg: return k.
2. Otherwise return 1 + min over x of max(drops(n - 1, x - 1), drops(n, k - x)).

class Solution {
    public int eggDrop(int n, int k) {
        if (k == 0 || k == 1) return k;          // 0 or 1 floor
        if (n == 1) return k;                    // one egg: go floor by floor
        int best = Integer.MAX_VALUE;
        for (int x = 1; x <= k; x++) {
            int breaks = eggDrop(n - 1, x - 1);  // look below with one egg fewer
            int survives = eggDrop(n, k - x);    // look above with the same eggs
            int worst = 1 + Math.max(breaks, survives);
            best = Math.min(best, worst);        // pick the floor with the best worst case
        }
        return best;
    }
}

How long it takes: every call loops over all floors and calls itself twice for each, so it blows up exponentially, around O(2^k). Extra room: the chain of calls, O(k).

Way 2: the clever way

There are only n * k different questions "e eggs, f floors". Fill them in a table dp[e][f], starting with 1 egg, then 2, and so on, and for each egg count with few floors first.

1. dp[1][f] = f and dp[e][0] = 0, dp[e][1] = 1.
2. For e from 2 to n, for f from 2 to k: dp[e][f] = 1 + min over x of max(dp[e-1][x-1], dp[e][f-x]).
3. The answer is dp[n][k].

The two boxes read for a try at floor x are one row up (fewer eggs) and earlier in the same row (fewer floors). Both are ready.

class Solution {
    public int eggDrop(int n, int k) {
        int[][] dp = new int[n + 1][k + 1];      // dp[e][f]: drops for e eggs, f floors
        for (int e = 1; e <= n; e++) {
            dp[e][0] = 0;                        // no floors
            dp[e][1] = 1;                        // one floor: one drop
        }
        for (int f = 1; f <= k; f++) dp[1][f] = f;   // one egg: floor by floor
        for (int e = 2; e <= n; e++) {
            for (int f = 2; f <= k; f++) {
                dp[e][f] = Integer.MAX_VALUE;
                for (int x = 1; x <= f; x++) {
                    int worst = 1 + Math.max(dp[e - 1][x - 1], dp[e][f - x]);
                    dp[e][f] = Math.min(dp[e][f], worst);
                }
            }
        }
        return dp[n][k];
    }
}

How long it takes: n * k boxes, each trying up to k floors, O(n * k^2). Extra room: the table, O(n * k).

Way 3: flip the question

Top companies and quant firms often push further. Instead of "how many drops for k floors?", ask "with m drops and e eggs, how many floors can I fully check?" Call it reach(m, e).

Drop once. If the egg breaks, the floors below must be checkable with m - 1 drops and e - 1 eggs. If it survives, the floors above must be checkable with m - 1 drops and e eggs. Plus the floor you dropped from:

reach(m, e) = reach(m - 1, e - 1) + reach(m - 1, e) + 1

Grow m until reach(m, n) is at least k. That m is the answer.

class Solution {
    public int eggDrop(int n, int k) {
        int[] reach = new int[n + 1];            // reach[e]: floors checkable with e eggs
        int moves = 0;
        while (reach[n] < k) {
            moves++;
            // go from many eggs to few, so reach[e - 1] is still the old value
            for (int e = n; e >= 1; e--) {
                reach[e] = reach[e - 1] + reach[e] + 1;
            }
        }
        return moves;
    }
}

How long it takes: n updates per drop, and the number of drops m is the answer, so O(n * m). With many eggs m is about log2(k). Extra room: O(n).

Watch out for

• One egg means floor by floor. Do not binary search with one egg: if it breaks on the first try you lose.
• Do not forget the + 1 for the drop you just made.
• In Way 3, update reach from the most eggs down to 1 egg, or reach[e - 1] is already the new value.

What interviewers ask next

• Speed up Way 2? For fixed e and f, dp[e-1][x-1] grows with x and dp[e][f-x] shrinks, so binary search the crossing point: O(n * k * log k).
• Why is 2 eggs and 100 floors 14? With m drops, 2 eggs reach m + (m-1) + ... + 1 = m(m+1)/2 floors. The smallest m with m(m+1)/2 >= 100 is 14.
• Is there a formula for reach? reach(m, e) = C(m, 1) + C(m, 2) + ... + C(m, e), a sum of binomial coefficients.
• Unlimited eggs? Then it is plain binary search: ceil(log2(k + 1)) drops.

Remember this

Grown-up words: "worst luck" is the worst case, min of max is a minimax choice, the chart is a 2D DP table over eggs and floors, and flipping the question means changing the DP state from floors to moves.