☕ DSA Java Articles

Topics › Dynamic Programming › MCM DP - Partition DP

Super Egg Drop

Medium TUF ID 1004 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You have k identical eggs and a building with floors 1 to n. There is an unknown critical floor f with 0 ≤ f ≤ n: an egg dropped from any floor above f breaks, and an egg dropped from floor f or below survives. In one move you drop an unbroken egg from a floor of your choice. A broken egg is gone; a surviving egg can be reused. Return the minimum number of moves that guarantees you learn f, no matter what f is.

Constraints (LeetCode 887): 1 ≤ k ≤ 100, 1 ≤ n ≤ 10^4.

“Minimum number of moves” is a worst-case quantity: we choose a strategy, an adversary chooses f, and we want the strategy whose worst case is smallest.

Example 1

k = 1, n = 2
answer = 2          // drop from 1; if it survives, drop from 2. With one egg you cannot skip floors.

Example 2

k = 2, n = 6
answer = 3          // drop from 3: if it breaks, try 1 then 2; if not, try 5, then 4 or 6

The recurrence: what happens after one drop?

Say we have k eggs and n floors still in doubt, and we drop from the x-th of those floors:

Only the number of floors in doubt matters, not their absolute heights, so the subproblem is again “(eggs, floors)”. We pay one move, and the adversary picks the worse outcome. We pick the best x:

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

The one-egg case is n because with a single egg you cannot risk skipping a floor: if you jump and it breaks, the floors you skipped are unresolved.

Approach 1: Recursion

Intuition. Try every floor for the next drop and take the best worst case.

Algorithm.

  1. Handle the base cases above.
  2. For each x in 1..n, compute 1 + max(recursion(k - 1, x - 1), recursion(k, n - x)).
  3. Return the minimum.
static int recursion(int k, int n) {
    if (n == 0 || n == 1) return n;                      // 0 floors: nothing to test; 1 floor: one drop
    if (k == 1) return n;                                // one egg: floor by floor from the bottom
    int best = Integer.MAX_VALUE;
    for (int x = 1; x <= n; x++) {
        int breaks = recursion(k - 1, x - 1);            // answer is below x, one egg fewer
        int survives = recursion(k, n - x);              // answer is above x, same eggs
        best = Math.min(best, 1 + Math.max(breaks, survives));
    }
    return best;
}

Complexity. Exponential time; already k = 2 costs about 2^n calls. Space O(n) for the stack. Only usable for toy sizes.

Approach 2: Memoization

Intuition. The state is (k, n): at most k × n values. Cache them.

Algorithm. Same recursion with a dp[k + 1][n + 1] table initialised to -1.

static int memoization(int k, int n) {
    int[][] dp = new int[k + 1][n + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(k, n, dp);
}

static int memo(int k, int n, int[][] dp) {
    if (n == 0 || n == 1) return n;
    if (k == 1) return n;
    if (dp[k][n] != -1) return dp[k][n];
    int best = Integer.MAX_VALUE;
    for (int x = 1; x <= n; x++) {
        best = Math.min(best, 1 + Math.max(memo(k - 1, x - 1, dp), memo(k, n - x, dp)));
    }
    return dp[k][n] = best;
}

Complexity. Time O(k × n^2): k × n states, each scanning n floors. Space O(k × n). For k = 100, n = 10^4 that is 10^10 steps, far too slow, so we need to speed up the inner loop.

Intuition. Look at the two terms inside the max as functions of x:

The maximum of a rising curve and a falling curve is smallest where they cross. So instead of scanning all x, binary search for the crossing: if breaks(mid) < survives(mid) the crossing is to the right, if breaks(mid) > survives(mid) it is to the left, and if they are equal we have found it. When the loop ends, the crossing lies between lo and hi, so the best x is one of them.

Algorithm.

  1. Base cases and cache lookup as before.
  2. Binary search x on [1, n] using the comparison above until lo + 1 ≥ hi.
  3. Evaluate both lo and hi; store and return the better one.
static int memoBinarySearch(int k, int n) {
    int[][] dp = new int[k + 1][n + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memoBs(k, n, dp);
}

static int memoBs(int k, int n, int[][] dp) {
    if (n == 0 || n == 1) return n;
    if (k == 1) return n;
    if (dp[k][n] != -1) return dp[k][n];
    // breaks(x) = memoBs(k-1, x-1) rises with x, survives(x) = memoBs(k, n-x) falls with x:
    // the best x sits where the two curves cross, so binary search for the crossing.
    int lo = 1, hi = n;
    while (lo + 1 < hi) {
        int mid = (lo + hi) >>> 1;
        int breaks = memoBs(k - 1, mid - 1, dp);
        int survives = memoBs(k, n - mid, dp);
        if (breaks < survives) lo = mid;
        else if (breaks > survives) hi = mid;
        else lo = hi = mid;
    }
    int best = Integer.MAX_VALUE;
    for (int x : new int[]{lo, hi}) {
        best = Math.min(best, 1 + Math.max(memoBs(k - 1, x - 1, dp), memoBs(k, n - x, dp)));
    }
    return dp[k][n] = best;
}

Complexity. Time O(k × n × log n): each state now does O(log n) work. Space O(k × n). This passes LeetCode, but the next idea is both faster and simpler.

Approach 4: Optimal, flip the question

Intuition. Instead of asking “how many moves do k eggs need for n floors?”, ask the inverse: “with m moves and e eggs, how many floors can I fully resolve?” Call that floors(m, e). Make the first drop from floor floors(m - 1, e - 1) + 1:

Counting the floor we dropped from, that gives

floors(m, e) = floors(m - 1, e - 1) + floors(m - 1, e) + 1,     floors(0, e) = floors(m, 0) = 0

and no choice of x is needed: the recurrence directly says where to drop. The answer is the smallest m with floors(m, k) ≥ n. We grow m one move at a time, keeping a single array over eggs. Updating e from high to low ensures floors[e - 1] on the right-hand side is still the value for m - 1 moves.

Algorithm.

  1. floors[0..k] = 0, moves = 0.
  2. While floors[k] < n: increment moves, then for e from k down to 1 set floors[e] = floors[e - 1] + floors[e] + 1.
  3. Return moves.
static int optimal(int k, int n) {
    int[] floors = new int[k + 1];                       // floors[e]: floors fully resolved with e eggs and `moves` drops
    int moves = 0;
    while (floors[k] < n) {
        moves++;
        for (int e = k; e >= 1; e--) {                   // descending so floors[e - 1] is still the previous move's value
            floors[e] = floors[e - 1] + floors[e] + 1;   // floors below (egg broke) + floors above (survived) + this floor
        }
    }
    return moves;
}

Dry run on Example 2 (k = 2, n = 6):

moves floors[1] floors[2] floors[2] ≥ 6?
0 0 0 no
1 1 1 no
2 2 3 no
3 3 6 yes, answer 3

With 3 moves and 2 eggs we drop first from floor floors(2, 1) + 1 = 3, which matches the strategy in the example.

Complexity. Time O(k × answer), and the answer is at most n (and about log2 n when eggs are plentiful). Space O(k). The values never overflow: we stop as soon as floors[k] ≥ n, and floors[e] ≤ floors[k], so every entry stays below 2n + 1.

A neat by-product: floors(m, e) = C(m, 1) + C(m, 2) + ... + C(m, e). With two eggs, m + m(m - 1)/2 ≥ 100 first holds at m = 14, the famous answer to the two-egg, 100-floor puzzle.

Edge cases and pitfalls