We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Egg Drop With 2 Eggs and N Floors

Difficulty: Medium

Problem Description

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. Return the minimum number of moves that you need to determine with certainty what the value of f is.

Key Insights

  • The problem can be solved using a dynamic programming approach.
  • We need to minimize the worst-case number of drops required to find the critical floor f.
  • The optimal strategy involves balancing the number of floors dropped and the remaining egg drops.
  • The solution uses a DP table where dp[k][m] represents the maximum number of floors that can be tested with k eggs and m moves.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

To solve the problem, we can use dynamic programming. We create a table dp where dp[k][m] indicates the maximum number of floors we can test with k eggs and m moves. The key idea is to use each drop wisely to maximize the number of floors that can be tested.

  1. If the egg breaks when dropped from a certain floor, we can only test the floors below it with one less egg.
  2. If the egg does not break, we can test the floors above it with the same number of eggs.
  3. The recurrence relation is:
    • dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1
  4. We want to find the smallest m such that dp[2][m] >= n.

Code Solutions

def eggDrop(n: int) -> int:
    # dp[i][j] will represent the maximum number of floors we can test with i eggs and j moves
    dp = [[0] * (n + 1) for _ in range(3)]  # We only need 2 eggs, so we use size 3 for simplicity
    m = 0  # number of moves

    while dp[2][m] < n:
        m += 1
        for k in range(2, 0, -1):  # Iterate backwards to avoid overwriting results
            dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1

    return m
← Back to All Questions