Skip to main content
On this page
Published Feb 3, 2026Updated Apr 21, 2026
AlgorithmsData StructuresComputer Science

K-Crystal Balls Problem: Drops, Floors, and the Optimal DP

The K-crystal balls problem — better known in the algorithms canon as the egg-drop problem — asks for the worst-case-optimal number of test drops needed to find a breaking-floor threshold when each broken test resource is permanently consumed. The two-egg case has a clean closed form , and the general case has a sharp dynamic-programming solution built on the recurrence , where is the maximum number of floors a budget of eggs and drops can resolve. This article derives both, walks the DP table, gives an algorithm, and shows where the model genuinely applies in production systems.

Worst-case drops to find a threshold among N floors as the egg budget k grows from 1 to infinity.
Worst-case drops to find a threshold among N floors as the egg budget k grows from 1 to infinity.

Problem Definition

Given identical, indistinguishable eggs (or crystal balls, or destructive probes) and a building with floors numbered , find the lowest floor from which an egg breaks. An egg dropped from floor either survives (and can be reused) or breaks (and is consumed forever). All eggs share the same unknown breaking floor.

The objective is the worst-case number of drops over an adversarially chosen .

Formal model
state    : (k, n) = (eggs remaining, floors still in scope)action   : pick a floor x in [1..n], drop an eggoutcome  : break  -> (k-1, x-1) below, scope = floors below x           hold   -> (k,   n-x) above, scope = floors above xgoal     : minimize the maximum drops to identify f*

The classic instance — eggs, floors — is featured in Knuth’s exercises, in Skiena’s coverage of dynamic programming, and as LeetCode 887 (“Super Egg Drop”) and LeetCode 1884 (“Egg Drop with 2 Eggs and N Floors”).

Note

The literature calls these eggs by convention. “Crystal balls” is the Frontend Masters / interview rebrand of the same model. Treat the two terms as synonyms.

Why Binary Search Fails

Binary search is optimal when each probe is non-destructive — the response narrows the search space symmetrically and you can keep probing. The egg-drop problem breaks that symmetry: a break both narrows the space and removes one of your only test resources.

Consider , , first drop at floor 50 (the binary-search choice):

  • If it survives: 1 egg consumed mentally, 50 floors remain, 2 eggs left — you can recurse.
  • If it breaks: 1 egg gone, 49 floors remain, only 1 egg left — you are now forced into a linear scan of floors 1..49. Worst case: drops.

Pure binary search gives drops in the worst case for . The optimum is dramatically better — 14 drops for — and the rest of the article derives why.

The asymmetry generalizes: at any state , dropping at floor exposes you to either the break branch (which loses an egg) or the hold branch (which loses floors). The optimum at is the floor that equalizes the worst case across both branches, not the floor that halves the floor count.

The Two-Egg Case

The case has the cleanest derivation and shows up most often in interviews and incident bisection. It is worth doing in full.

Setting up the recurrence

Let be the floor of the very first drop. There are two cases.

  1. Egg #1 breaks at . Egg #2 must linearly scan floors to identify . Worst case: drops.
  2. Egg #1 holds at . Floor is somewhere in . We are now in state and the next drop is some floor with — because if it broke there, egg #2 would scan a window of size and the total would be , which must stay to keep our worst case bounded by .

Continuing inductively, the optimal first-egg drops are at floors

The largest reachable floor after drops is

We need this sum to cover all floors:

Solving the quadratic:

For : , so . And indeed .

Why a fixed jump is not optimal

A common first attempt is “jump by each time, then linear scan”. For that is jumps of 10 with worst case drops. The decreasing-step plan above bounds the worst case at 14 drops — five fewer.

The improvement comes from spending later drops on smaller windows: by the time egg #1 has survived drops, it has already used drops, so the second egg can only afford more — meaning the next jump must shrink to keep the window walkable in steps.

Decision tree

Decision tree for the optimal k=2 plan with N=100, showing how every leaf is bounded by 14 drops.
Decision tree for the optimal k=2 plan with N=100; every leaf is bounded by 14 drops.

Concrete trace

For with threshold :

Trace of the optimal k=2 plan for N=100 finding threshold 37 in 13 drops.
Trace of the optimal k=2 plan for N=100 finding threshold 37 in 13 drops, well within the worst-case bound of 14.

Naive Dynamic Programming

For arbitrary , the textbook DP works directly on .

Let be the minimum worst-case drops for eggs and floors. From the case analysis above:

with base cases for , , .

naive-dp.ts
function minDropsNaive(k: number, n: number): number {  const dp: number[][] = Array.from({ length: k + 1 }, () =>    new Array(n + 1).fill(0)  )  for (let i = 1; i <= n; i++) dp[1][i] = i  for (let e = 2; e <= k; e++) {    for (let f = 1; f <= n; f++) {      let best = Infinity      for (let x = 1; x <= f; x++) {        const worst = 1 + Math.max(dp[e - 1][x - 1], dp[e][f - x])        if (worst < best) best = worst      }      dp[e][f] = best    }  }  return dp[k][n]}

The inner loop scans all candidate floors , so the runtime is . With memoization on the recurrence the implementation is the same complexity by another path. A quadrangle-inequality / Knuth-style optimization shrinks the inner search to amortized constant (GeeksforGeeks: Egg Dropping Puzzle DP-11), giving — but a much cleaner falls out by inverting the state.

The Optimal Flip: Drops -> Floors

Instead of asking “given eggs and floors, what is the minimum number of drops?”, ask the dual:

Given eggs and drops, what is the maximum number of floors that can be guaranteed-resolved?

Once we have , the answer to the original question is the smallest with , found by simple search.

Recurrence

Suppose we have eggs and drops and we drop the first egg from some floor. There are exactly two outcomes, and we get to design the floor so both outcomes use the remaining budget optimally.

  • If the egg breaks, we have eggs and drops; we can resolve floors below the test floor.
  • If the egg holds, we have eggs and drops; we can resolve floors above the test floor.
  • The test floor itself contributes 1.

So

with (no eggs, no resolution) and (no drops, no resolution).

This is the recurrence proved in the Brilliant: Egg Dropping wiki and used by the canonical solution to LeetCode 887.

Cell dependency diagram for the floors-covered DP: every cell f(k, m) reads its left and lower-left neighbors.
Cell dependency for f(k, m) = f(k-1, m-1) + f(k, m-1) + 1; fill in increasing m, then increasing k.

Closed form: a binomial sum

Unrolling the recurrence yields

Inductive proof sketch. Base case matches the empty sum. Inductive step using Pascal’s identity :

For this collapses to , recovering the two-egg closed form derived earlier. For the sum exceeds already at , so the egg budget no longer binds and binary search is optimal.

Floors-covered growth

Each added egg unlocks a new binomial term and accelerates coverage. The numbers below are for :

drops
4 4 10 14 15
7 7 28 63 98
10 10 55 175 385
13 13 91 377 1092
14 14 105 469 1470

By , four eggs already cover more than a thousand floors, while two eggs are still under 100. The row is dominated by , the row by — a polynomial-degree explosion per added egg until the binary-search ceiling at kicks in.

Algorithms and Complexity

Approach Time Space Notes
Pure recursion, no memo exponential Pedagogical only.
DP on with min-max scan Direct from the original recurrence; works but slow.
DP with binary search on the inner Uses monotonicity of and in .
Flipped DP on (tabulation) Fill columns of until .
Binomial sum + binary search on Canonical LeetCode 887 solution; uses the closed form above.

The algorithm is dominant in practice. It binary-searches and at each candidate computes incrementally, short-circuiting once the partial sum exceeds .

Worked Examples

k = 2, N = 100

Closed form: . Verify: , . So 14 drops are necessary and sufficient.

k = 3, N = 100

We need the smallest with .
7 7 21 35 63
8 8 28 56 92
9 9 36 84 129

So but — three eggs need 9 drops worst case for 100 floors, beating two eggs (14) by a third.

k = 7, N = 100

, so seven eggs suffice in drops — the binary-search lower bound. Adding more eggs cannot help.

Implementation

k-crystal-balls.ts
// Closed-form first drop for k = 2, N floors.function firstDropTwoEggs(n: number): number {  return Math.ceil((-1 + Math.sqrt(1 + 8 * n)) / 2)}// Run the optimal k = 2 plan against a sorted boolean array of length n.// Returns the index of the threshold floor, or -1 if none.function twoEggThreshold(floors: boolean[]): number {  const n = floors.length  let step = firstDropTwoEggs(n)  let pos = step - 1 // 0-indexed  let lastSafe = -1  while (pos < n) {    if (floors[pos]) {      for (let i = lastSafe + 1; i < pos; i++) {        if (floors[i]) return i      }      return pos    }    lastSafe = pos    step -= 1    if (step <= 0) break    pos += step  }  return -1}// O(k * log N) minimum drops for k eggs and N floors.// Binary-searches the smallest m with sum_{i=1..k} C(m, i) >= n.function minDrops(k: number, n: number): number {  if (n === 0) return 0  if (k === 0) return Infinity  if (k === 1) return n  const floorsCoveredCapped = (m: number): number => {    let sum = 0    let term = 1    for (let i = 1; i <= k; i++) {      term = (term * (m - i + 1)) / i      sum += term      if (sum >= n) return n    }    return sum  }  let lo = 1  let hi = n  while (lo < hi) {    const mid = (lo + hi) >> 1    if (floorsCoveredCapped(mid) >= n) hi = mid    else lo = mid + 1  }  return lo}

Tip

For very large , compute the binomial product in floating point with the running-quotient form above and short-circuit at the cap; for cryptographic-scale use BigInt arithmetic to avoid loss of precision in the partial sum.

Edge Cases

Condition Behavior
No probes possible; the threshold cannot be identified. Return Infinity.
Linear scan only. Worst case = drops.
Trivially 0 drops.
One drop settles the threshold.
Binary search saturates the bound; extra eggs are unused.
Floating-point drift Use BigInt or the capped running product for .

Real-World Applications

The egg-drop model maps cleanly onto any threshold-detection problem where a failed test is more expensive than a successful one. Read each application carefully — the literal “broken egg” interpretation is rare.

Reliability and destructive testing

Find the load, voltage, or temperature at which a system fails, with a strict budget of destructive runs (hardware burnt, customer-visible incident triggered, account locked out). Each destructive trial is genuinely consumed; the egg-drop model applies one-to-one and the DP gives the tightest run-budget.

Path MTU discovery (loose analogy)

Find the largest packet a path will accept without fragmentation. A probe larger than the path MTU is dropped — like a ball breaking — but it can be retried, so the resource is not strictly consumed. The cost asymmetry (a failed probe burns an RTT plus possible retransmission) still motivates a similar bias toward bigger jumps early. Real implementations of PMTUD (RFC 1191) and Packetization Layer PMTUD (RFC 4821) explicitly avoid pure binary search and use plateau tables of common MTUs because of this asymmetry.

Software version bisection (loose analogy)

git bisect is binary search — each test is non-destructive, so the egg-drop model does not apply. The model becomes relevant only when builds themselves are expensive and parallel: with build agents you can probe candidates per round and treat each “bad” result as committing one agent to a smaller window. Even then, parallel binary search is usually a better mental model than the egg-drop DP.

Database tuning and capacity probing

Find the selectivity threshold at which an index becomes beneficial, or the throughput at which p99 latency falls off a cliff, with a fixed budget of benchmark runs. Each benchmark consumes wall-clock time and possibly disrupts neighboring tenants. With a fixed test budget, the schedule gives the tightest probing plan that still bounds the worst-case number of disruptions.

Practical Takeaways

  • Re-frame “minimum drops for floors” as “maximum floors for drops” — the DP becomes one-line and the closed form falls out.
  • For , memorize and the decreasing-step plan starting at .
  • For general , prefer the binomial-sum search over any DP — it is shorter, faster, and numerically stable with capped accumulation.
  • The egg budget saturates at . Beyond that, binary search is optimal and extra eggs are dead weight.
  • The model only literally applies when a failed test is really consumed; for “expensive but repeatable” tests it is a useful upper bound, not a tight one.

References