Egg dropping

Hard

Problem

You have e eggs and a building with f floors. An egg breaks when dropped from any floor above an unknown threshold. Return the minimum number of drops that guarantees you find the threshold, in the worst case.

Example 1

Input:  e = 2, f = 10
Output: 4

Example 2

Input:  e = 2, f = 100
Output: 14

Also asked as: Egg Dropping Problem

Test cases

Case 1

Input:    2, 10
Expected: 4

Case 2

Input:    2, 100
Expected: 14

Case 3

Input:    1, 5
Expected: 5

Case 4

Input:    2, 1
Expected: 1

Case 5

Input:    3, 0
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DP over (eggs, floors)

Time O(e·f²)Space O(e·f)

dp[e][f] = min trials to be sure with e eggs and f floors. Drop from floor x: egg breaks → dp[e−1][x−1], survives → dp[e][f−x]; take the worst, minimise over x.

function eggDrop(eggs, floors) {
const dp = Array.from({ length: eggs + 1 }, () => new Array(floors + 1).fill(0));
for (let f = 1; f <= floors; f++) dp[1][f] = f;
for (let e = 2; e <= eggs; e++)
for (let f = 1; f <= floors; f++) {
dp[e][f] = Infinity;
for (let x = 1; x <= f; x++)
dp[e][f] = Math.min(dp[e][f], 1 + Math.max(dp[e - 1][x - 1], dp[e][f - x]));
}
return dp[eggs][floors];
}

O(e·f) version: dp[e][trials] = max floors coverable; increase trials until dp[eggs][trials] ≥ floors.