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.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Binary Search
- Asked at: Amazon, Google, Myntra, Goldman Sachs
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1001 <= n <= 10^4
Hints for Super Egg Drop
Hint 1
Turn the question around: with
mmoves andeeggs, what is the largest number of floors whose critical floor you can always pin down?Hint 2
Make the first drop. If the egg breaks you keep
m - 1moves ande - 1eggs for the floors below; if it survives,m - 1moves andeeggs for the floors above. Sofloors(m, e) = floors(m-1, e-1) + floors(m-1, e) + 1.Hint 3
Raise
mone at a time, updating a one-dimensional array over eggs frome = kdown to1(so the previous move's values are still intact), and stop at the firstmwithfloors(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
- Keep an array
floors[0..k], all zero (zero moves resolve zero floors). - Repeat: increment
moves; forefromkdown to1, setfloors[e] = floors[e] + floors[e - 1] + 1. - Stop as soon as
floors[k] >= nand returnmoves.
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. fcan be 0 (every floor breaks the egg), which is whynfloors needfloors(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 movesJava
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