Two Eggs, 100 Floors

In one line

Every drop of the first egg spends one of your drops, so each gap should be one floor shorter than the last: 14, 27, 39, and so on. Flip the question to "how many floors can d drops cover?" and the same idea solves any number of eggs.

time O(√n)space O(1)

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

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$ .

The algorithm

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$ .

Complexity

Time

O (k \cdot d)

d rounds of k updates, where d is the answer: about √(2n) for two eggs, about log₂ n once eggs are plentiful.

Space

O (k)

One running count per egg.

With two eggs that's $O(\sqrt{n})$ time and constant space.

Common pitfalls

1
Reaching for binary search
It's optimal only when a failed probe costs nothing. With two eggs, the first break drops you to a linear walk, and binary search's first probe puts that walk at half the building.
2
Stopping at fixed √n steps
Steps of $\sqrt{n}$ give about $2\sqrt{n}$ drops, 19 for 100 floors. Shrinking the step by one each time gets $\sqrt{2n}$ , 14. Same idea, about a quarter fewer drops.
3
The textbook DP over floors
The direct recurrence tries every floor $x$ for the next drop and takes $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 to "floors per drop count" is what makes it fast.
4
Minimizing the average
The question is the guaranteed bound. A strategy that's usually quick but occasionally needs 20 drops loses to one that always needs 14.

Practice, easiest first

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

Two Eggs, 100 Floors

Why the obvious strategies lose

Balance the worst case

Flip the question

The algorithm

Complexity

Common pitfalls

Practice, easiest first

What's next in the notebook?

Hashing and the Birthday Paradox

Valid Triangle Number

3Sum

Two Sum II

Container With Most Water

Two Pointers