Egg dropping
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
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.