Egg Drop With 2 Eggs and N Floors

justyy (81)in #programming • 3 years ago

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.

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

Constraints:
1 <= n <= 1000

Hints
Is it really optimal to always drop the egg on the middle floor for each move?
Can we create states based on the number of unbroken eggs and floors to build our solution?

Pythons Top Down Dynamic Programming to Compute Egg Drops with 2 Eggs

Given two egges, if we drop at floor i - there are two situations:

If the egg breaks, we have i floors to try with 1 egg. The answer is i + 1.

If the egg doesnt break, we have n - i - 1 floors with 2 eggs, The answer is f(n - i - i) + 1.

The answer is the minimum of both.

class Solution:
    @cache
    def twoEggDrop(self, n: int) -> int:
        if n == 1 or n == 2:
            return n
        ans = math.inf
        for i in range(1, n + 1):
            ans = min(ans, 1 + max(i, self.twoEggDrop(n - i - 1)))
        return ans

We use the Recursion with Memoization which is aka Top Down Dynamic Programming Algorithm.

See also: Google’s Two Egg’s Problem

Reposted to Blog