Egg Dropping Puzzle

Find the minimum drops needed in the worst case to find the critical floor. Dropping from floor x either breaks the egg (search below with one fewer egg) or it survives (search above with the same eggs) — take the worse outcome, then pick x to minimise that.

Category

Dynamic Programming

Time complexity

O(eggs · floors²)

Space complexity

O(eggs · floors)

Pseudocode

dp[1][f] = f (one egg: linear search)
dp[e][0] = 0 (no floors, no drops)
dp[e][f] = 1 + min over x of
  max(dp[e-1][x-1], dp[e][f-x])

Reference implementation

for e in range(2, eggs+1):
  for f in range(1, floors+1):
    dp[e][f] = min(1 + max(dp[e-1][x-1], dp[e][f-x])
        for x in range(1, f+1))

Open the interactive Egg Dropping Puzzle visualisation →