1074 Advanced

1074-egg-drop — Egg Drop

Functional Programming

Tutorial

The Problem

Given k eggs and n floors, find the minimum number of trials needed to determine the critical floor above which eggs break. This is a classic DP/binary-search problem that appears in reliability testing, threshold determination, and A/B test stopping rules.

The naive O(kn²) DP can be improved to O(kn log n) using binary search, and further to O(kn) with a rolling-minimum approach.

🎯 Learning Outcomes

• Model the egg drop problem as a DP with state (eggs, floors)

• Implement the O(kn²) DP and understand the recurrence

• Optimize to O(kn log n) with binary search on the drop floor

• Understand the "worst case" minimax nature: minimize(maximum(break, survive))

• Connect to binary search theory and reliability testing

Code Example

#![allow(clippy::all)]
// 1074: Egg Drop — DP + Binary Search

// Approach 1: Basic DP O(k*n^2)
fn egg_drop_basic(eggs: usize, floors: usize) -> usize {
    let mut dp = vec![vec![0usize; floors + 1]; eggs + 1];
    for i in 1..=eggs {
        for j in 1..=floors {
            if i == 1 {
                dp[i][j] = j;
            } else {
                dp[i][j] = usize::MAX;
                for x in 1..=j {
                    let worst = 1 + dp[i - 1][x - 1].max(dp[i][j - x]);
                    dp[i][j] = dp[i][j].min(worst);
                }
            }
        }
    }
    dp[eggs][floors]
}

// Approach 2: DP with binary search O(k*n*log(n))
fn egg_drop_bs(eggs: usize, floors: usize) -> usize {
    let mut dp = vec![vec![0usize; floors + 1]; eggs + 1];
    for i in 1..=eggs {
        for j in 1..=floors {
            if i == 1 {
                dp[i][j] = j;
            } else {
                let (mut lo, mut hi) = (1, j);
                while lo < hi {
                    let mid = (lo + hi) / 2;
                    if dp[i - 1][mid - 1] < dp[i][j - mid] {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
                dp[i][j] = 1 + dp[i - 1][lo - 1].max(dp[i][j - lo]);
            }
        }
    }
    dp[eggs][floors]
}

// Approach 3: Optimal — how many floors can we check with t trials and k eggs?
fn egg_drop_optimal(eggs: usize, floors: usize) -> usize {
    // dp[t][k] = max floors checkable with t trials and k eggs
    let mut dp = vec![vec![0usize; eggs + 1]; floors + 1];
    for t in 1..=floors {
        for k in 1..=eggs {
            dp[t][k] = 1 + dp[t - 1][k - 1] + dp[t - 1][k];
            if dp[t][k] >= floors && k == eggs {
                return t;
            }
        }
    }
    floors // fallback (1 egg case)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        assert_eq!(egg_drop_basic(1, 10), 10);
        assert_eq!(egg_drop_basic(2, 10), 4);
        assert_eq!(egg_drop_basic(2, 6), 3);
        assert_eq!(egg_drop_basic(3, 14), 4);
    }

    #[test]
    fn test_binary_search() {
        assert_eq!(egg_drop_bs(1, 10), 10);
        assert_eq!(egg_drop_bs(2, 10), 4);
        assert_eq!(egg_drop_bs(2, 6), 3);
    }

    #[test]
    fn test_optimal() {
        assert_eq!(egg_drop_optimal(1, 10), 10);
        assert_eq!(egg_drop_optimal(2, 10), 4);
        assert_eq!(egg_drop_optimal(2, 6), 3);
        assert_eq!(egg_drop_optimal(2, 100), 14);
    }
}

(* 1074: Egg Drop — DP + Binary Search *)

(* Approach 1: Basic DP O(k*n^2) *)
let egg_drop_basic eggs floors =
  let dp = Array.init (eggs + 1) (fun _ -> Array.make (floors + 1) 0) in
  for i = 1 to eggs do
    for j = 1 to floors do
      if i = 1 then dp.(i).(j) <- j
      else begin
        dp.(i).(j) <- max_int;
        for x = 1 to j do
          let worst = 1 + max dp.(i - 1).(x - 1) dp.(i).(j - x) in
          dp.(i).(j) <- min dp.(i).(j) worst
        done
      end
    done
  done;
  dp.(eggs).(floors)

(* Approach 2: DP with binary search O(k*n*log(n)) *)
let egg_drop_bs eggs floors =
  let dp = Array.init (eggs + 1) (fun _ -> Array.make (floors + 1) 0) in
  for i = 1 to eggs do
    for j = 1 to floors do
      if i = 1 then dp.(i).(j) <- j
      else begin
        let lo = ref 1 and hi = ref j in
        while !lo < !hi do
          let mid = (!lo + !hi) / 2 in
          let broke = dp.(i - 1).(mid - 1) in
          let survived = dp.(i).(j - mid) in
          if broke < survived then lo := mid + 1
          else hi := mid
        done;
        let x = !lo in
        dp.(i).(j) <- 1 + max dp.(i - 1).(x - 1) dp.(i).(j - x)
      end
    done
  done;
  dp.(eggs).(floors)

(* Approach 3: Optimal DP — how many floors can we check with t trials and k eggs? *)
let egg_drop_optimal eggs floors =
  (* dp.(t).(k) = max floors checkable with t trials and k eggs *)
  let dp = Array.init (floors + 1) (fun _ -> Array.make (eggs + 1) 0) in
  let t = ref 0 in
  while dp.(!t).(eggs) < floors do
    incr t;
    for k = 1 to eggs do
      dp.(!t).(k) <- 1 + dp.(!t - 1).(k - 1) + dp.(!t - 1).(k)
    done
  done;
  !t

let () =
  assert (egg_drop_basic 1 10 = 10);
  assert (egg_drop_basic 2 10 = 4);
  assert (egg_drop_basic 2 6 = 3);
  assert (egg_drop_basic 3 14 = 4);

  assert (egg_drop_bs 1 10 = 10);
  assert (egg_drop_bs 2 10 = 4);
  assert (egg_drop_bs 2 6 = 3);

  assert (egg_drop_optimal 1 10 = 10);
  assert (egg_drop_optimal 2 10 = 4);
  assert (egg_drop_optimal 2 6 = 3);
  assert (egg_drop_optimal 2 100 = 14);

  Printf.printf "✓ All tests passed\n"

Key Differences

**max_int / usize::MAX**: Both use a large sentinel as infinity for minimization; Rust's usize::MAX saturates on addition — use explicit comparison to avoid overflow.

Binary search optimization: The transition point derivation is purely mathematical; both languages implement lo/hi bisection identically.

Alternative formulation: The "k eggs, t trials → how many floors" DP (dp[t][k] += dp[t-1][k-1] + dp[t-1][k]) is cleaner — only requires O(kn) instead of O(kn²) DP.

Practical applications: Reliability testing (how many tests to find a failure threshold), canary deployments (how many % rollouts to find a regression floor).

OCaml Approach

let egg_drop eggs floors =
  let dp = Array.make_matrix (eggs+1) (floors+1) 0 in
  for i = 1 to eggs do
    for j = 1 to floors do
      if i = 1 then dp.(i).(j) <- j
      else begin
        dp.(i).(j) <- max_int;
        for x = 1 to j do
          let worst = 1 + max dp.(i-1).(x-1) dp.(i).(j-x) in
          if worst < dp.(i).(j) then dp.(i).(j) <- worst
        done
      end
    done
  done;
  dp.(eggs).(floors)

Identical structure. The binary search optimization has the same mathematical basis in both languages.

Full Source

#![allow(clippy::all)]
// 1074: Egg Drop — DP + Binary Search

// Approach 1: Basic DP O(k*n^2)
fn egg_drop_basic(eggs: usize, floors: usize) -> usize {
    let mut dp = vec![vec![0usize; floors + 1]; eggs + 1];
    for i in 1..=eggs {
        for j in 1..=floors {
            if i == 1 {
                dp[i][j] = j;
            } else {
                dp[i][j] = usize::MAX;
                for x in 1..=j {
                    let worst = 1 + dp[i - 1][x - 1].max(dp[i][j - x]);
                    dp[i][j] = dp[i][j].min(worst);
                }
            }
        }
    }
    dp[eggs][floors]
}

// Approach 2: DP with binary search O(k*n*log(n))
fn egg_drop_bs(eggs: usize, floors: usize) -> usize {
    let mut dp = vec![vec![0usize; floors + 1]; eggs + 1];
    for i in 1..=eggs {
        for j in 1..=floors {
            if i == 1 {
                dp[i][j] = j;
            } else {
                let (mut lo, mut hi) = (1, j);
                while lo < hi {
                    let mid = (lo + hi) / 2;
                    if dp[i - 1][mid - 1] < dp[i][j - mid] {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
                dp[i][j] = 1 + dp[i - 1][lo - 1].max(dp[i][j - lo]);
            }
        }
    }
    dp[eggs][floors]
}

// Approach 3: Optimal — how many floors can we check with t trials and k eggs?
fn egg_drop_optimal(eggs: usize, floors: usize) -> usize {
    // dp[t][k] = max floors checkable with t trials and k eggs
    let mut dp = vec![vec![0usize; eggs + 1]; floors + 1];
    for t in 1..=floors {
        for k in 1..=eggs {
            dp[t][k] = 1 + dp[t - 1][k - 1] + dp[t - 1][k];
            if dp[t][k] >= floors && k == eggs {
                return t;
            }
        }
    }
    floors // fallback (1 egg case)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        assert_eq!(egg_drop_basic(1, 10), 10);
        assert_eq!(egg_drop_basic(2, 10), 4);
        assert_eq!(egg_drop_basic(2, 6), 3);
        assert_eq!(egg_drop_basic(3, 14), 4);
    }

    #[test]
    fn test_binary_search() {
        assert_eq!(egg_drop_bs(1, 10), 10);
        assert_eq!(egg_drop_bs(2, 10), 4);
        assert_eq!(egg_drop_bs(2, 6), 3);
    }

    #[test]
    fn test_optimal() {
        assert_eq!(egg_drop_optimal(1, 10), 10);
        assert_eq!(egg_drop_optimal(2, 10), 4);
        assert_eq!(egg_drop_optimal(2, 6), 3);
        assert_eq!(egg_drop_optimal(2, 100), 14);
    }
}

(* 1074: Egg Drop — DP + Binary Search *)

(* Approach 1: Basic DP O(k*n^2) *)
let egg_drop_basic eggs floors =
  let dp = Array.init (eggs + 1) (fun _ -> Array.make (floors + 1) 0) in
  for i = 1 to eggs do
    for j = 1 to floors do
      if i = 1 then dp.(i).(j) <- j
      else begin
        dp.(i).(j) <- max_int;
        for x = 1 to j do
          let worst = 1 + max dp.(i - 1).(x - 1) dp.(i).(j - x) in
          dp.(i).(j) <- min dp.(i).(j) worst
        done
      end
    done
  done;
  dp.(eggs).(floors)

(* Approach 2: DP with binary search O(k*n*log(n)) *)
let egg_drop_bs eggs floors =
  let dp = Array.init (eggs + 1) (fun _ -> Array.make (floors + 1) 0) in
  for i = 1 to eggs do
    for j = 1 to floors do
      if i = 1 then dp.(i).(j) <- j
      else begin
        let lo = ref 1 and hi = ref j in
        while !lo < !hi do
          let mid = (!lo + !hi) / 2 in
          let broke = dp.(i - 1).(mid - 1) in
          let survived = dp.(i).(j - mid) in
          if broke < survived then lo := mid + 1
          else hi := mid
        done;
        let x = !lo in
        dp.(i).(j) <- 1 + max dp.(i - 1).(x - 1) dp.(i).(j - x)
      end
    done
  done;
  dp.(eggs).(floors)

(* Approach 3: Optimal DP — how many floors can we check with t trials and k eggs? *)
let egg_drop_optimal eggs floors =
  (* dp.(t).(k) = max floors checkable with t trials and k eggs *)
  let dp = Array.init (floors + 1) (fun _ -> Array.make (eggs + 1) 0) in
  let t = ref 0 in
  while dp.(!t).(eggs) < floors do
    incr t;
    for k = 1 to eggs do
      dp.(!t).(k) <- 1 + dp.(!t - 1).(k - 1) + dp.(!t - 1).(k)
    done
  done;
  !t

let () =
  assert (egg_drop_basic 1 10 = 10);
  assert (egg_drop_basic 2 10 = 4);
  assert (egg_drop_basic 2 6 = 3);
  assert (egg_drop_basic 3 14 = 4);

  assert (egg_drop_bs 1 10 = 10);
  assert (egg_drop_bs 2 10 = 4);
  assert (egg_drop_bs 2 6 = 3);

  assert (egg_drop_optimal 1 10 = 10);
  assert (egg_drop_optimal 2 10 = 4);
  assert (egg_drop_optimal 2 6 = 3);
  assert (egg_drop_optimal 2 100 = 14);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        assert_eq!(egg_drop_basic(1, 10), 10);
        assert_eq!(egg_drop_basic(2, 10), 4);
        assert_eq!(egg_drop_basic(2, 6), 3);
        assert_eq!(egg_drop_basic(3, 14), 4);
    }

    #[test]
    fn test_binary_search() {
        assert_eq!(egg_drop_bs(1, 10), 10);
        assert_eq!(egg_drop_bs(2, 10), 4);
        assert_eq!(egg_drop_bs(2, 6), 3);
    }

    #[test]
    fn test_optimal() {
        assert_eq!(egg_drop_optimal(1, 10), 10);
        assert_eq!(egg_drop_optimal(2, 10), 4);
        assert_eq!(egg_drop_optimal(2, 6), 3);
        assert_eq!(egg_drop_optimal(2, 100), 14);
    }
}

Deep Comparison

Egg Drop — Comparison

Core Insight

The egg drop problem asks for worst-case minimum trials. The key insight for the optimal solution: instead of asking "given k eggs and n floors, what's the minimum trials?", ask "given t trials and k eggs, what's the maximum floors we can check?" This gives the recurrence f(t,k) = 1 + f(t-1,k-1) + f(t-1,k).

OCaml Approach

• 2D array DP with nested loops

• ref cells for binary search pointers

• max_int as initial sentinel for minimization

• while loop with ref counter for optimal approach

Rust Approach

• 2D vec! DP table

• Binary search with tuple destructuring let (mut lo, mut hi)

• usize::MAX as sentinel

• Early return from nested loop for optimal approach

• Method chaining .max() and .min()

Comparison Table

Aspect	OCaml	Rust
Sentinel	`max_int`	`usize::MAX`
Binary search	`ref` pointers + `while`	`let (mut lo, mut hi)` + `while`
Min/max	`min`/`max` functions	`.min()`/`.max()` methods
Optimal loop	`while dp.(!t).(eggs) < floors`	`for t in 1..=floors` + early return
Early exit	Increment `ref` counter	`return t` from inner loop

Exercises

Implement the dp[t][k] formulation: minimum trials t such that dp[t][k] >= n, which avoids the O(n²) inner loop.

Add path reconstruction: return not just the minimum trials but also the sequence of floors to try.

Generalize to "weighted egg drop" where breaking an egg on floor f costs cost[f] — find the minimum expected cost.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust