# Two Eggs and an 80-Floor Building: Optimal Drop Strategy

Source: https://www.techinterview.org/post/3233459669/5-unbreakable-light-bulbs-and-a-80-floor-building/
Updated: 2026-04-27 · techinterview.org

## The Two-Eggs (Light Bulbs) Problem: 80-Floor Building, Optimal Strategy, and DP

"You have 2 eggs and a 100-floor building. Find the highest floor an egg can be dropped from without breaking, using as few drops as possible." This puzzle — also stated with light bulbs — is a classic interview question at finance tech, FAANG, and quant trading firms. The naive answer (linear scan) is O(n); the binary search answer (O(log n)) doesn't apply because once an egg breaks, you can't reuse it. The elegant answer uses a quadratic-spaced strategy that reduces worst-case drops to O(√n). This guide covers the standard approaches, the math behind the optimal strategy, and the dynamic-programming generalization to k eggs.

## Problem Statement

You have 2 eggs (or 2 light bulbs, etc.) and an n-floor building. There exists a critical floor F such that:

- Eggs dropped from floor ≤ F survive.

- Eggs dropped from floor > F break.

Find F. Eggs that survive can be reused; eggs that break are gone. Minimize the worst-case number of drops needed.

For the variant in the title: 80 floors, 2 eggs.

## Approach 1: Naive Linear Scan

Drop from floor 1, 2, 3, ... until an egg breaks. Then F is one less than the floor that broke. Worst case: n drops.

Doesn't use the second egg cleverly. Acceptable as a warm-up; interviewers will push for better.

## Approach 2: Binary Search (Doesn't Work)

Drop from floor n/2. If it breaks, you have one egg left and must linear-scan floors 1 to n/2 - 1. Worst case: n/2 + 1 drops.

Better than naive but not optimal. The "binary search" intuition fails because losing an egg restricts the second phase to a linear scan.

## Approach 3: Optimal Strategy (Square Root)

Drop the first egg at floors x, 2x, 3x, .... If the first egg breaks at floor kx, linear-scan from (k-1)x + 1 to kx - 1 (at most x - 1 drops).

Worst case = (drops to find the breaking interval) + (drops within the interval). For floor F discovered after k jumps then x-1 linear:

worst_case(x) = ceil(n / x) + (x - 1)

Minimize over x: take derivative, set to zero, get x ≈ √n. For n = 100, x = 10 gives worst case 19. For n = 80, x = 9 gives worst case ~9 + 8 = 17.

To minimize worst case across all possible F values (not just one specific F), use a sequence with decreasing step sizes — each successive jump should add one less floor than the previous, so the total drops at every breaking point is the same.

### Optimal step-decreasing sequence

If the worst case is k drops, the first egg's drops are at floors:

- k

- k + (k - 1) = 2k - 1

- k + (k - 1) + (k - 2) = 3k - 3

- ...

The sum k + (k-1) + ... + 1 = k(k+1)/2 must cover at least n. For n = 100: k(k+1)/2 ≥ 100, so k ≥ 14 (since 14×15/2 = 105). For n = 80: k(k+1)/2 ≥ 80, so k ≥ 13 (13×14/2 = 91).

So for 80 floors, 2 eggs, worst case is 13 drops. Strategy: drop at floors 13, 25, 36, 46, 55, 63, 70, 76, 80. If the egg breaks at any step, scan the previous gap with the second egg.


```
def min_drops_2_eggs(n: int) -> int:
    """Minimum worst-case drops for 2 eggs in an n-floor building."""
    k = 1
    while k * (k + 1) // 2 < n:
        k += 1
    return k


# Tests
print(min_drops_2_eggs(100))  # 14
print(min_drops_2_eggs(80))   # 13
print(min_drops_2_eggs(36))   # 8
```


## Approach 4: Dynamic Programming for k Eggs

(LeetCode #887 — Super Egg Drop) Generalize to k eggs and n floors.


```
def super_egg_drop(k: int, n: int) -> int:
    """O(k * n^2) DP — naive."""
    # dp[i][j] = max floors solvable with i eggs in j drops
    dp = [[0] * (n + 1) for _ in range(k + 1)]
    moves = 0
    while dp[k][moves] < n:
        moves += 1
        for eggs in range(1, k + 1):
            dp[eggs][moves] = dp[eggs - 1][moves - 1] + dp[eggs][moves - 1] + 1
    return moves


# Tests
print(super_egg_drop(1, 2))   # 2
print(super_egg_drop(2, 6))   # 3
print(super_egg_drop(3, 14))  # 4
print(super_egg_drop(2, 100)) # 14
```


**Why this DP works:** with i eggs and j moves, maximum floors solvable = (floors solvable below the drop point with i-1 eggs and j-1 moves) + (floors solvable above with i eggs and j-1 moves) + 1 (the drop floor itself).

**Complexity:** O(k × log n) when implemented with the inverse-function trick. The naive DP is O(k × n²); LeetCode's tight constraints require the optimization.

## Common Variations

### Find the maximum floors with given drops

Given k eggs and m drops, what's the maximum n you can determine? Same DP, read it the other way.

### Real-life lightbulb stress testing

The actual problem statement varies by interviewer. Sometimes "2 light bulbs," sometimes "2 eggs," sometimes "2 drones." The math is identical.

### Probabilistic variants

Suppose drops only sometimes break the egg. Different problem; expected number of drops, not worst case. Bayesian or Monte Carlo simulation.

## Common Mistakes

- **Treating it as binary search.** Binary search assumes you can always probe arbitrarily; eggs are limited. The problem requires reasoning about the cost of losing an egg.

- **Computing the wrong worst case.** The worst case must consider the least-favorable F. Using the average-case strategy gives lower numbers but doesn't answer the worst-case question.

- **Forgetting the interior linear scan.** After the first egg breaks at floor kx, you must scan floor (k-1)x + 1 through kx - 1 — that's x - 1 drops, not x. Off-by-one common.

- **Using a constant step size when decreasing-step is optimal.** The square-root approximation gives roughly the right answer but not the optimal one. The decreasing-step sequence is what gets you the lowest worst case.

- **Confusing "at least k drops" with "exactly k drops."** The minimum worst case is the smallest k such that k(k+1)/2 ≥ n. Not k(k-1)/2 or k².

## Frequently Asked Questions

### What's the expected interview answer for 2 eggs, 100 floors?

  14 drops worst case, using the decreasing-step strategy: drop at floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99. Walk through the math: k(k+1)/2 ≥ n. Strong candidates derive this; weak candidates default to "split in half" without explaining why it's suboptimal.

### How does the answer change for k eggs?

  With more eggs, you can use binary-search-like strategies. The DP gives the exact minimum drops. With k eggs and unlimited drops, you can solve up to 2^k - 1 floors with k drops (binary search). For typical interview questions, k = 2 is most common; k = 3 occasionally; arbitrary k is the LeetCode #887 question.

### Why is √n the wrong (suboptimal) answer?

  √n optimizes for a single-step strategy (drop at floor x, 2x, 3x, ...). The decreasing-step strategy performs slightly better because it balances worst-case across all possible F values. The improvement is small for small n but matters for the cleanest answer.

### How does this generalize to other k?

  For k = 1, you must linear-scan: n drops. For k = 2, use decreasing steps: O(√n). For k = log n, you can binary-search: O(log n). Higher k doesn't reduce drops below log n. The DP makes this concrete.

### Why do interviewers like this problem?

  It tests whether you can resist "binary search" reflex when the problem structure breaks the assumption. It also tests whether you recognize a cost function (worst case = jumps + linear) and can minimize it analytically. Strong candidates derive the decreasing-step idea; weaker candidates default to constant steps; weakest candidates linear-scan. The gradient of solutions makes it useful as an interview signal.

See also: [Three People on a Weak Bridge](/post/3233459680/three-people-on-a-weak-bridge/) • [A Man with Burning Ropes](/post/3233459689/a-man-with-burning-ropes/) • [Fair Server Processing](/post/3233459683/server-to-process-fair-number-of-functions/)