The Two Egg Drop Problem: Why the Answer Is 14

You have two identical eggs and a building with 100 floors. There's some floor $f$ at or below which an egg survives a drop, and above which it breaks ( $f$ can be 0, if every drop breaks it, or 100, if none do). An egg that survives can be dropped again. A broken one is gone.

What's the fewest drops that guarantees you find $f$ , however unlucky you are?

"However unlucky" is the whole problem. You're not minimizing the average, you're minimizing the worst case, and the adversary picks $f$ after seeing your strategy.

Why the obvious strategies lose

With one egg there's only one safe strategy: start at floor 1 and go up one at a time. The first break tells you $f$ . Skip a floor and a break leaves you unable to tell which of the two floors did it. So one egg costs up to 100 drops.

The second egg is what buys you speed: you can use the first one to take big jumps, and fall back to the careful floor-by-floor walk with the second once the first breaks.

Strategy for the first egg	Drops at	Worst case
None (one egg, walk up)	1, 2, 3, ...	100
Binary search	50, then 75 if it survives	50
Fixed steps of 10	10, 20, ..., 100	19
Shrinking steps	14, 27, 39, 50, ...	14

Binary search is the instinct, and it's the worst of the jumping strategies. Drop at 50 and it breaks: you have one egg left and 49 floors below, which is 49 more drops, one at a time. Binary search assumes a failed probe is cheap. Here the first failure costs you half your tools.

Steps of 10 do much better. The worst case is when the first egg survives nine times and breaks at 100: that's 10 drops, then 9 more walking 91 to 99. But notice the imbalance. If it breaks on the very first drop, at 10, you only need 9 more: 10 total. Fixed steps make late breaks expensive and early breaks cheap. The worst case is set by the expensive end.

Balance the worst case

Plot the total cost against which drop breaks the first egg, and the problem with fixed steps is obvious:

@itsnas total-drops-by-when-the-first-egg-breaks.svg

Fixed steps make late breaks expensive. Shrinking each gap by one floor makes every break cost the same 14.

Every time the first egg survives, you've spent a drop. So the next gap should be one floor shorter, to keep the total the same whichever drop it breaks on.

Say the answer is $d$ drops. The first drop goes at floor $d$ : if it breaks, the second egg walks floors 1 to $d-1$ , $d$ drops total. If it survives, you have $d-1$ drops left, so the next drop goes $d-1$ floors higher, then $d-2$ , and so on down to 1. The floors you can cover add up to

d + (d-1) + \dots + 1 = \frac{d(d+1)}{2} \ge n

(1) Floors covered with d drops and two eggs must reach n.

For $n = 100$ : $13 \cdot 14 / 2 = 91$ falls short, $14 \cdot 15 / 2 = 105$ clears it. So 14 drops, with the first egg going at 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100.

Check it at a couple of points. Break at 14: walk 1 to 13, that's $1 + 13 = 14$ . Break at 27: walk 15 to 26, that's $2 + 12 = 14$ . Every break costs the same total. That's what balanced means.

It's also a proof that 13 can't work. With 13 drops the first one has to be at floor 13 or lower (a break there leaves 12 drops for the floors below). The next can be at most 12 floors higher, and so on. The furthest you can reach is $13 + 12 + \dots + 1 = 91$ , and a building with 100 floors has nine you'd never test.

Flip the question

"Fewest drops for $n$ floors" is awkward to compute directly. The inverse is easy: with $d$ drops and $k$ eggs, how many floors can you fully cover? Call it $F(d, k)$ .

Make one drop, from some floor. Either the egg breaks, and you have $d-1$ drops and $k-1$ eggs for the floors below; or it survives, and you have $d-1$ drops and $k$ eggs for the floors above. Plus the floor you just tested:

F(d, k) = F(d-1, k-1) + F(d-1, k) + 1

(2) Floors coverable with d drops and k eggs.

with $F(0, k) = 0$ (no drops, no floors) and $F(d, 0) = 0$ (no eggs, no floors).

With one egg, $F(d, 1) = d$ : the walk up. With two, the recurrence gives $F(d, 2) = d + F(d-1, 2)$ , which unrolls to $d + (d-1) + \dots + 1$ , exactly equation (1). The general answer is a sum of binomial coefficients:

F(d, k) = \sum_{i=1}^{k} \binom{d}{i}

(3) Closed form for any number of eggs.

It follows from equation (2) by Pascal's rule, $\binom{d-1}{i-1} + \binom{d-1}{i} = \binom{d}{i}$ , with the $+1$ supplying the $\binom{d-1}{0}$ term.

Give yourself as many eggs as drops ( $k = d$ ) and equation (3) becomes $\sum_{i=1}^{d} \binom{d}{i} = 2^d - 1$ .

Counting floors, one drop at a time

1
Keep covered[k], the floors checkable with the drops so far and $k$ eggs.
2
Add one drop and update every covered[k] with equation (2).
3
Stop as soon as covered[eggs] reaches the number of floors.

@itsnas egg-drop.ts

codeegg-drop.ts

// Fewest drops that always find the critical floor (eggs >= 1).
function minDrops(eggs: number, floors: number): number {
  // covered[k]: floors fully checkable with `drops` drops, k eggs
  const covered = new Array<number>(eggs + 1).fill(0)
  let drops = 0
 
  while (covered[eggs] < floors) {
    drops++
    for (let k = eggs; k >= 1; k--) {
      covered[k] = covered[k - 1] + covered[k] + 1
    }
  }
 
  return drops
}
 
minDrops(2, 100) // 14

main

Nas (@itsnas)

// Fewest drops that always find the critical floor (eggs >= 1).
fn min_drops(eggs: usize, floors: u64) -> u64 {
    // covered[k]: floors fully checkable with `drops` drops, k eggs
    let mut covered = vec![0u64; eggs + 1];
    let mut drops = 0;
 
    while covered[eggs] < floors {
        drops += 1;
        for k in (1..=eggs).rev() {
            covered[k] = covered[k - 1] + covered[k] + 1;
        }
    }
 
    drops
}
 
min_drops(2, 100); // 14

main

Nas (@itsnas)

// Fewest drops that always find the critical floor (eggs >= 1).
int minDrops(int eggs, long long floors) {
  // covered[k]: floors fully checkable with `drops` drops, k eggs
  std::vector<long long> covered(eggs + 1, 0);
  int drops = 0;
 
  while (covered[eggs] < floors) {
    drops++;
    for (int k = eggs; k >= 1; k--) {
      covered[k] = covered[k - 1] + covered[k] + 1;
    }
  }
 
  return drops;
}
 
minDrops(2, 100); // 14

main

Nas (@itsnas)

// Fewest drops that always find the critical floor (eggs >= 1).
func minDrops(eggs int, floors int64) int {
	// covered[k]: floors fully checkable with `drops` drops, k eggs
	covered := make([]int64, eggs+1)
	drops := 0
 
	for covered[eggs] < floors {
		drops++
		for k := eggs; k >= 1; k-- {
			covered[k] = covered[k-1] + covered[k] + 1
		}
	}
 
	return drops
}
 
minDrops(2, 100) // 14

main

Nas (@itsnas)

# Fewest drops that always find the critical floor (eggs >= 1).
def min_drops(eggs: int, floors: int) -> int:
    # covered[k]: floors fully checkable with `drops` drops, k eggs
    covered = [0] * (eggs + 1)
    drops = 0
 
    while covered[eggs] < floors:
        drops += 1
        for k in range(eggs, 0, -1):
            covered[k] = covered[k - 1] + covered[k] + 1
 
    return drops
 
min_drops(2, 100)  # 14

main

Nas (@itsnas)

For two eggs specifically you can skip the loop and solve equation (1) for $d$ directly: $d = \lceil (\sqrt{8n + 1} - 1) / 2 \rceil$ , which for $n = 100$ is $\lceil 13.65 \rceil = 14$ .

$O(k \cdot d)$ time, where $d$ is the answer (about $\sqrt{2n}$ for two eggs, about $\log_2 n$ once eggs are plentiful), and $O(k)$ space.

The textbook DP instead tries every floor for the next drop, $1 + \min_x \max(T(k-1, x-1), T(k, n-x))$ . It's correct and $O(k n^2)$ , too slow for Super Egg Drop's $n = 10^4$ . Flipping the question to "floors per number of drops" is what makes it fast, and it's the move worth keeping: when the direct question is hard, ask how much a given budget can buy.

Egg Drop With 2 Eggs and N FloorsMedium

Guess Number Higher or Lower IIMedium

Super Egg DropHard

More algorithms and math

Hashing and the Birthday Paradox

The Two Egg Drop Problem: Why the Answer Is 14

Why the obvious strategies lose

Balance the worst case

Flip the question

Counting floors, one drop at a time

Invert This Binary Tree (For a CRUD Job)

Hashing and the Birthday Paradox

Valid Triangle Number

3Sum