Skip to main content

887. Super Egg Drop

hard

Find the minimum number of moves to determine the critical floor in a k-egg, n-floor egg drop problem. Inverted 2D DP — dp[m][k] = the maximum number of floors you can resolve with m moves and k eggs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given k identical eggs and you have access to a building with n floors labeled from 1 to n. You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break. Each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves. Return the minimum number of moves that you need to determine with certainty what the value of f is.

Constraints

  • 1 <= k <= 100
  • 1 <= n <= 10^4

Examples

Example 1

Input
k = 1, n = 2
Output
2

Explanation: Drop the egg from floor 1. If it breaks, we know that f = 0. Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1. If it does not break, then we know f = 2. Hence, we need at minimum 2 moves to determine with certainty what the value of f is.

Example 2

Input
k = 2, n = 6
Output
3

Example 3

Input
k = 3, n = 14
Output
4

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive dp[k][n] (eggs left, floors left) with min-over-floors is O(k * n^2) — too slow.

Hint 2

Invert the question. dp[m][k] = maximum number of floors you can cover with m moves and k eggs. Then find the smallest m with dp[m][k] >= n.

Hint 3

Recurrence: dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1. (drop an egg: it breaks -> dp[m-1][k-1] floors below; it survives -> dp[m-1][k] floors above; plus the current floor itself.)

Hint 4

Grow m until dp[m][k] >= n. m is at most O(log n) for large k and O(n) for k = 1.

Solution approach

Reveal approach

Inverted DP. dp[m][k] is the maximum number of floors resolvable with m moves and k eggs. Recurrence: with one drop, if the egg breaks you can resolve dp[m-1][k-1] floors below; if it survives you can resolve dp[m-1][k] floors above; plus the current floor counts as 1. So dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1. Initialize dp[0][*] = 0 and dp[*][0] = 0. Loop m = 1, 2, ... and update dp[m][k] for each k from 1 to K, stopping as soon as dp[m][K] >= n; return m. Because dp[m][k] grows roughly like (m choose k), m stays O((n)^(1/k)) and the loop is fast even for n = 10^4. Space optimization: a 1D dp[k] updated right-to-left works since dp[m][k] depends on the previous m only.

Complexity

Time
O(k * log n)
Space
O(k)

Related patterns

  • dynamic-programming
  • binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Goldman Sachs

Practice these live with InterviewChamp.AI

Drill Super Egg Drop and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →