Taro Logo

Egg Drop With 2 Eggs and N Floors

Medium
Meta logo
Meta
Topics:
Dynamic Programming

You are given two 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.

In 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.

What is the minimum number of moves that you need to determine with certainty what the value of f is?

Example 1:

Input: n = 2 Output: 2 Explanation: We can drop the first egg from floor 1 and the second egg from floor 2. If the first egg breaks, we know that f = 0. If the second egg breaks but the first egg didn't, we know that f = 1. Otherwise, if both eggs survive, we know that f = 2.

Example 2:

Input: n = 100 Output: 14 Explanation: One optimal strategy is:

  • Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting from floor 1 and going up one at a time to find f within 8 more drops. Total drops is 1 + 8 = 9.
  • If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9 and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more drops. Total drops is 2 + 12 = 14.
  • If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, and 100.

Regardless of the outcome, it takes at most 14 drops to determine f.

Solution


Egg Dropping Problem

Problem Description

You are given two identical eggs and a building with n floors labeled from 1 to n. There exists a floor f (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. You want to determine the minimum number of moves needed to find f with certainty.

Naive Approach (Brute Force)

The simplest approach is to perform a linear search. Drop the first egg from floor 1, then floor 2, and so on. If the egg breaks at floor x, then f = x - 1. If the egg doesn't break until floor n, then f = n. However, this approach doesn't leverage the fact that you have two eggs and won't result in an optimal solution.

Optimal Approach (Dynamic Programming)

We can solve this problem using dynamic programming. Let dp[i][j] be the minimum number of moves needed to determine f with i eggs and j floors.

Base Cases:

  • dp[1][j] = j: With one egg, we must try each floor sequentially.
  • dp[i][0] = 0: If there are no floors, no moves are needed.
  • dp[i][1] = 1: If there is one floor, one move is needed.

Recursive Relation:

For each floor x (1 <= x <= j), we have two possibilities:

  1. The egg breaks: We now have i - 1 eggs and x - 1 floors to check. The number of moves in this case is dp[i - 1][x - 1] + 1.
  2. The egg doesn't break: We now have i eggs and j - x floors to check. The number of moves in this case is dp[i][j - x] + 1.

We want to minimize the worst-case scenario, so we take the maximum of these two possibilities for each x and then minimize over all x:

dp[i][j] = min(max(dp[i - 1][x - 1], dp[i][j - x]) + 1) for all 1 <= x <= j

Edge Cases:

  • n = 1: Return 1.
  • n = 0: Return 0.

Code Implementation (Python):

def egg_drop(n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(3)]  # Only need to store 2 rows

    for j in range(1, n + 1):
        dp[1][j] = j

    for i in range(2, 3):
        for j in range(1, n + 1):
            dp[i][j] = float('inf')
            for x in range(1, j + 1):
                dp[i][j] = min(dp[i][j], max(dp[i - 1][x - 1], dp[i][j - x]) + 1)

    return dp[2][n]

# Example usage
n = 100
result = egg_drop(n)
print(f"Minimum number of moves for n={n}: {result}")

Complexity Analysis

  • Time Complexity: O(kn^2), where k is the number of eggs (in this case, k=2) and n is the number of floors. The nested loops iterate through the possible egg and floor combinations.
  • Space Complexity: O(kn) where k is the number of eggs and n is the number of floors. In this specific case, since the number of eggs is fixed at 2, space complexity is O(n).

Further Optimization (Mathematical approach - Optional)

It is also possible to use a mathematical approach, but that is not generally expected in an interview. For k drops and e eggs, the number of floors that can be checked in worst case is C(k, 1) + C(k, 2) + .... + C(k, e) where C(n,r) represents the binomial coefficient "n choose r". Therefore, we need to find the smallest k for which the above expression is n or larger.