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

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

See also: Three People on a Weak Bridge • A Man with Burning Ropes • Fair Server Processing