Super Egg Drop

hard dynamic programming egg drop math

Problem

You have k identical eggs and a building with n floors. There is a critical floor f (0 ≤ f ≤ n): an egg dropped from a floor above f breaks, and an egg dropped at or below f does not. You may reuse an egg that did not break. Return the minimum number of moves needed to determine f with certainty in the worst case.

Inputk = 2, n = 6

Output3

With 2 eggs, 3 moves can certainly distinguish among 7 outcomes (floors 0..6), so 3 moves suffice for 6 floors.

k (eggs)

n (floors)

def super_egg_drop(k, n):
    dp = [0] * (k + 1)
    moves = 0
    while dp[k] < n:
        moves += 1
        for e in range(k, 0, -1):
            dp[e] = dp[e] + dp[e - 1] + 1
    return moves

function superEggDrop(k, n) {
  const dp = new Array(k + 1).fill(0);
  let moves = 0;
  while (dp[k] < n) {
    moves++;
    for (let e = k; e >= 1; e--) {
      dp[e] = dp[e] + dp[e - 1] + 1;
    }
  }
  return moves;
}

class Solution {
    public int superEggDrop(int k, int n) {
        int[] dp = new int[k + 1];
        int moves = 0;
        while (dp[k] < n) {
            moves++;
            for (int e = k; e >= 1; e--) {
                dp[e] = dp[e] + dp[e - 1] + 1;
            }
        }
        return moves;
    }
}

int superEggDrop(int k, int n) {
    vector<int> dp(k + 1, 0);
    int moves = 0;
    while (dp[k] < n) {
        moves++;
        for (int e = k; e >= 1; e--) {
            dp[e] = dp[e] + dp[e - 1] + 1;
        }
    }
    return moves;
}

Explanation

The usual question — "fewest moves for k eggs and n floors" — is easier when you flip it around: with a fixed number of moves and eggs, what is the most floors you could possibly resolve? This solution grows that number until it covers n.

Let dp[e] be the maximum number of floors solvable with e eggs and the current number of moves. We keep increasing moves by one and updating each entry until dp[k] ≥ n.

The recurrence per new move is dp[e] = dp[e] + dp[e-1] + 1. The reasoning: drop one egg on a chosen floor. If it breaks, you have e-1 eggs and the remaining moves to handle the floors below (dp[e-1]); if it survives, you handle the floors above with e eggs (the old dp[e]); and +1 counts the floor you just tested. We update from high e to low so each uses the previous-move values.

Example: k = 2, n = 6. After enough moves dp[2] reaches 1, 3, then 6 at moves = 3 — so 3 moves suffice for 6 floors, the answer.

Each move does O(k) work and the floor count grows fast, so the move count needed is about √n, giving the O(k·√n) running time.

Time: O(k · √n) Space: O(k)