Super Egg Drop

Hard
1502.

Super Egg Drop

Super Egg Drop is a hard coding problem on dynamic programming, math and binary search, asked in Amazon, Google, Myntra and Goldman Sachs interviews.

You have k identical eggs and a building with floors numbered 1 to n. Somewhere there is a critical floor f with 0 <= f <= n: an egg dropped from any floor above f breaks, and an egg dropped from floor f or below survives.

In one move you take an unbroken egg and drop it from a floor of your choice. A broken egg is gone for good; an egg that survives can be dropped again.

Return the minimum number of moves that is enough to determine f exactly, no matter what its value is.

Example 1

Input
k = 1, n = 3
Output
3
Explanation
With a single egg you cannot risk skipping a floor: drop from 1, then 2, then 3.

Example 2

Input
k = 2, n = 10
Output
4
Explanation
Drop the first egg from 4, then 7, then 9, then 10. When it breaks, walk the second egg up through the floors just above the last safe drop — never more than 4 moves in total.

Example 3

Input
k = 3, n = 25
Output
5

Constraints

  • 1 <= k <= 100
  • 1 <= n <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
var superEggDrop = function(k, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Super Egg Drop — Solution in Python, Java & C++

Super Egg Drop solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Super Egg Drop is a hard coding problem on dynamic programming, math and binary search, asked in Amazon, Google, Myntra and Goldman Sachs interviews.

Problem statement

You have k identical eggs and a building with floors numbered 1 to n. Somewhere there is a critical floor f with 0 <= f <= n: an egg dropped from any floor above f breaks, and an egg dropped from floor f or below survives.

In one move you take an unbroken egg and drop it from a floor of your choice. A broken egg is gone for good; an egg that survives can be dropped again.

Return the minimum number of moves that is enough to determine f exactly, no matter what its value is.

Example 1

Input: k = 1, n = 3
Output: 3
Explanation: With a single egg you cannot risk skipping a floor: drop from 1, then 2, then 3.

Example 2

Input: k = 2, n = 10
Output: 4
Explanation: Drop the first egg from 4, then 7, then 9, then 10. When it breaks, walk the second egg up through the floors just above the last safe drop — never more than 4 moves in total.

Example 3

Input: k = 3, n = 25
Output: 5

Constraints

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

Hints for Super Egg Drop

  1. Hint 1

    Turn the question around: with m moves and e eggs, what is the largest number of floors whose critical floor you can always pin down?

  2. Hint 2

    Make the first drop. If the egg breaks you keep m - 1 moves and e - 1 eggs for the floors below; if it survives, m - 1 moves and e eggs for the floors above. So floors(m, e) = floors(m-1, e-1) + floors(m-1, e) + 1.

  3. Hint 3

    Raise m one at a time, updating a one-dimensional array over eggs from e = k down to 1 (so the previous move's values are still intact), and stop at the first m with floors(m, k) >= n.

How to solve Super Egg Drop

Asking for the fewest moves for n floors is hard to recurse on directly; the inverse question is easy. Let floors(m, e) be the most floors that m moves and e eggs can fully resolve. The first drop splits the building into the floors below (handled with one fewer egg if it breaks) and the floors above (same eggs if it survives), plus the floor dropped from.

Approach

  1. Keep an array floors[0..k], all zero (zero moves resolve zero floors).
  2. Repeat: increment moves; for e from k down to 1, set floors[e] = floors[e] + floors[e - 1] + 1.
  3. Stop as soon as floors[k] >= n and return moves.

Why it works

With m moves and e eggs, drop the first egg from floor floors(m-1, e-1) + 1. If it breaks, the critical floor is below and floors(m-1, e-1) floors remain for e - 1 eggs; if not, the floors above number at most floors(m-1, e). Both branches are covered, so floors(m, e) = floors(m-1, e-1) + floors(m-1, e) + 1 is achievable — and no strategy can do better, because any first drop leaves one of those two subproblems. The answer is the first m for which floors(m, k) reaches n, and since floors grows at least linearly (and exponentially with two or more eggs), the loop is short.

Complexity

  • Time — O(k · m), where m is the answer (at most n, and about log2 n once k is large)
  • Space — O(k)

Pitfalls

  • The direct DP over (eggs, floors) with a linear scan over the first drop is O(k · n^2) — far too slow for n = 10^4.
  • Update the egg array from high to low; going upward would read this move's value of floors[e - 1] instead of the previous move's.
  • f can be 0 (every floor breaks the egg), which is why n floors need floors(m, k) >= n, not > n.

Reference solution

Python

def superEggDrop(k: int, n: int) -> int:
    floors = [0] * (k + 1)
    moves = 0
    while floors[k] < n:
        moves += 1
        for e in range(k, 0, -1):
            floors[e] += floors[e - 1] + 1
    return moves

Java

public static int superEggDrop(int k, int n) {
    int[] floors = new int[k + 1];
    int moves = 0;
    while (floors[k] < n) {
        moves++;
        for (int e = k; e >= 1; e--) floors[e] = floors[e] + floors[e - 1] + 1;
    }
    return moves;
}

C++

int superEggDrop(int k, int n) {
    vector<int> floors(k + 1, 0);
    int moves = 0;
    while (floors[k] < n) {
        moves++;
        for (int e = k; e >= 1; e--) floors[e] = floors[e] + floors[e - 1] + 1;
    }
    return moves;
}

JavaScript

var superEggDrop = function(k, n) {
    var floors = new Array(k + 1).fill(0);
    var moves = 0;
    while (floors[k] < n) {
        moves++;
        for (var e = k; e >= 1; e--) floors[e] = floors[e] + floors[e - 1] + 1;
    }
    return moves;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Binary Search