Egg Drop With 2 Eggs and N Floors — Problem & Solution
Egg Drop With 2 Eggs and N Floors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Egg Drop With 2 Eggs and N Floors is a medium coding problem on dynamic programming and math, asked in Amazon, Google and Goldman Sachs interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math
- Asked at: Amazon, Google, 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 two identical eggs and a building with floors 1 to n. There is an unknown floor f with 0 <= f <= n: an egg dropped from any floor higher than f breaks, and an egg dropped from floor f or lower survives.
In one move you drop an unbroken egg from any floor. A broken egg is gone; an egg that survives can be dropped again.
Return the minimum number of moves that guarantees you find f exactly, whatever its value.
Example 1
Input: n = 2
Output: 2
Explanation: Drop from floor 1: if it breaks, f = 0; otherwise drop from floor 2 to decide between f = 1 and f = 2.
Example 2
Input: n = 100
Output: 14
Explanation: Drop the first egg from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 — each step 1 shorter — and scan with the second egg after it breaks.
Example 3
Input: n = 1
Output: 1
Constraints
1 <= n <= 1000
Hints for Egg Drop With 2 Eggs and N Floors
Hint 1
Once the first egg breaks, the second egg must test the floors in between one at a time, from the bottom up.
Hint 2
If you are allowed
kmoves in total, the first drop can be at most from floork(otherwise a break leaves too many floors to scan). After it survives, the next jump can be at mostk - 1floors, and so on.Hint 3
So
kmoves coverk + (k - 1) + ... + 1 = k(k + 1) / 2floors. Find the smallestkwithk(k + 1) / 2 >= n— or use the DPdp[m] = min over x of 1 + max(x - 1, dp[m - x]).
How to solve Egg Drop With 2 Eggs and N Floors
With k moves and two eggs, the first egg's drops must shrink by one floor each time, so k moves can resolve at most k(k + 1) / 2 floors — and that many is achievable.
Approach
- Start with
k = 0. - While
k(k + 1) / 2 < n, increasek. - Return
k.
Why it works
Suppose k moves remain and both eggs are intact. If the first egg breaks on its drop, the second egg has k - 1 moves to test every floor below one by one, so the drop can be at most k - 1 floors above the last safe floor — that is, it covers k floors in its gap. If it survives, the problem repeats with k - 1 moves. So the floors covered are at most k + (k - 1) + ... + 1, and dropping exactly at those gaps achieves it. The equivalent DP dp[m] = min over x of 1 + max(x - 1, dp[m - x]) gives the same numbers.
Complexity
- Time —
O(sqrt(n)) - Space —
O(1)
Pitfalls
- Binary search on floors is wrong here: after the first egg breaks there is only one egg left, which must be used linearly.
fmay be 0 (every floor breaks the egg) — the count of possibilities isn + 1, which the triangular bound already accounts for.
Reference solution
Python
def twoEggDrop(n: int) -> int:
k = 0
while k * (k + 1) // 2 < n:
k += 1
return kJava
public static int twoEggDrop(int n) {
int k = 0;
while (k * (k + 1) / 2 < n) k++;
return k;
}C++
int twoEggDrop(int n) {
int k = 0;
while (k * (k + 1) / 2 < n) k++;
return k;
}JavaScript
var twoEggDrop = function(n) {
var k = 0;
while (k * (k + 1) / 2 < n) k++;
return k;
};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