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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Super Egg Drop

Number: 923

Difficulty: Hard

Paid? No

Companies: Amazon, Goldman Sachs, Oracle, Google

Problem Description

You are given k identical eggs and a building with n floors. You need to find the minimum number of moves required to determine with certainty the highest floor (f) from which an egg can be dropped without breaking. Any egg dropped from a floor higher than f will break, and any egg dropped at or below f will not break.

Key Insights

  • When an egg is dropped, there are two outcomes: it either breaks or it doesn't.
  • If an egg breaks from a certain floor, the problem reduces to the lower floors with one fewer egg.
  • If an egg doesn’t break, we can explore the floors above with the same number of eggs.
  • A dynamic programming approach based on the number of moves provides a more efficient solution than testing floor by floor.
  • Use the recurrence: dp[k][m] = 1 + dp[k-1][m-1] + dp[k][m-1] where dp[k][m] represents the maximum number of floors that can be checked with k eggs and m moves.

Space and Time Complexity

Time Complexity: O(k * m) where m is the minimum number of moves required (in worst-case scenario m can be O(n) when k=1). Space Complexity: O(k) by using a one-dimensional DP array iterated over the number of moves.

Solution

We use dynamic programming where instead of directly computing the minimum moves needed for n floors, we compute the maximum number of floors that can be determined using m moves and k eggs. The recurrence relation is:

dp[k][m] = 1 + dp[k-1][m-1] + dp[k][m-1]

This formula is based on the fact that if an egg is dropped:

  • It breaks: We have one less egg and one move less; hence dp[k-1][m-1].
  • It does not break: We still have k eggs and one move less; hence dp[k][m-1].

We add one for the current floor. We keep increasing m until dp[k][m] is at least n. This approach efficiently finds the answer.

Code Solutions

# Python solution using dynamic programming.
def superEggDrop(k, n):
    # dp[m] will hold maximum number of floors that can be checked with given eggs and m moves.
    dp = [0] * (k + 1)
    moves = 0
    
    # Continue until we can cover n floors.
    while dp[k] < n:
        moves += 1
        # Iterate backwards so we use previous results without overwriting data we still need.
        for eggs in range(k, 0, -1):
            # Update the dp for current move number.
            dp[eggs] = dp[eggs] + dp[eggs - 1] + 1
    return moves

# Line-by-line usage example:
# k = 2, n = 6 should return 3.
print(superEggDrop(2, 6))
← Back to All Questions