Egg Drop With 2 Eggs and N Floors

medium dp math

Problem

You have two identical eggs and a building with n floors numbered 1 to n (1 ≤ n ≤ 1000). There is an unknown threshold floor f with 0 ≤ f ≤ n: any egg dropped from a floor above f breaks, while an egg dropped from floor f or below survives and can be dropped again.

Each move you drop one egg from a floor of your choice; a broken egg is gone for good. Return the minimum number of moves that guarantees you can determine f, no matter what its value is.

Inputn = 8

Output4

Three drops with two eggs can only separate 3 + 2 + 1 = 6 floors, so 8 floors need 4 drops (for example, first drops at floors 4 and 7, then a linear scan).

n (number of floors)

def two_egg_drop(n):
    # dp[i] = fewest worst-case drops with 2 eggs and i floors
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        best = float('inf')
        for x in range(1, i + 1):
            # break at x   -> scan the x-1 floors below, one egg left
            # survive at x -> i-x floors above, still two eggs
            cost = 1 + max(x - 1, dp[i - x])
            best = min(best, cost)
        dp[i] = best
    return dp[n]

function twoEggDrop(n) {
  // dp[i] = fewest worst-case drops with 2 eggs and i floors
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    let best = Infinity;
    for (let x = 1; x <= i; x++) {
      // break at x -> x-1 linear drops below; survive -> dp[i-x] above
      best = Math.min(best, 1 + Math.max(x - 1, dp[i - x]));
    }
    dp[i] = best;
  }
  return dp[n];
}

int twoEggDrop(int n) {
    // dp[i] = fewest worst-case drops with 2 eggs and i floors
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int best = Integer.MAX_VALUE;
        for (int x = 1; x <= i; x++) {
            // break at x -> x-1 linear drops below; survive -> dp[i-x] above
            best = Math.min(best, 1 + Math.max(x - 1, dp[i - x]));
        }
        dp[i] = best;
    }
    return dp[n];
}

int twoEggDrop(int n) {
    // dp[i] = fewest worst-case drops with 2 eggs and i floors
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int best = INT_MAX;
        for (int x = 1; x <= i; x++) {
            // break at x -> x-1 linear drops below; survive -> dp[i-x] above
            best = min(best, 1 + max(x - 1, dp[i - x]));
        }
        dp[i] = best;
    }
    return dp[n];
}

Explanation

Let dp[i] be the fewest drops that always suffice with 2 eggs and i floors. The decision is only ever where to make the first drop. If we drop at floor x, two things can happen, and an adversary picks the worse one: the egg breaks, or it survives.

If it breaks at x, only one egg remains, so we cannot risk skipping any floor — we must scan floors 1 through x−1 from the bottom, costing x − 1 more drops. If it survives, the threshold lies among the i − x floors above, and we still own two eggs, which is exactly the subproblem dp[i − x]. So a first drop at x costs 1 + max(x − 1, dp[i − x]), and dp[i] is the minimum of that over all x from 1 to i. The two arms pull against each other: raising x makes the break case dearer and the survive case cheaper, and the optimum balances them.

Walking the default example n = 8: dp[1] = 1, dp[2] = 2, then dp[3] = 2 (drop at 2: break costs 1, survive leaves dp[1] = 1). The values grow slowly — dp[4..6] = 3, dp[7] = 4 — and finally dp[8] = 1 + max(1, dp[6] = 3) = 4. The bars in the visualization show every candidate first-drop floor for the current i; the orange bar is the cheapest worst case.

There is also a pure-math shortcut hiding here. If we are allowed k drops, the first drop can safely go at floor k (a break leaves k−1 scans), the next k−1 floors higher, and so on, covering k + (k−1) + … + 1 = k(k+1)/2 floors. The answer is the smallest k with k(k+1)/2 ≥ n; for n = 8, k = 4 because 6 < 8 ≤ 10. The DP rediscovers this triangular-number pattern on its own.

The DP fills n entries and tries up to i candidate floors for each, giving O(n²) time with an O(n) one-dimensional table — comfortably fast for n ≤ 1000, while the closed form above would answer in O(1).

Time: O(n²) Space: O(n)