Egg Drop With 2 Eggs and N Floors

Medium
1625.

Egg Drop With 2 Eggs and N Floors

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.

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
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} n
 * @return {number}
 */
var twoEggDrop = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Once the first egg breaks, the second egg must test the floors in between one at a time, from the bottom up.

  2. Hint 2

    If you are allowed k moves in total, the first drop can be at most from floor k (otherwise a break leaves too many floors to scan). After it survives, the next jump can be at most k - 1 floors, and so on.

  3. Hint 3

    So k moves cover k + (k - 1) + ... + 1 = k(k + 1) / 2 floors. Find the smallest k with k(k + 1) / 2 >= n — or use the DP dp[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

  1. Start with k = 0.
  2. While k(k + 1) / 2 < n, increase k.
  3. 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.
  • f may be 0 (every floor breaks the egg) — the count of possibilities is n + 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 k

Java

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