Egg Drop With 2 Eggs and N Floors


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.

1
2
3
4
5
6
7
8
9
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
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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
430 words
Last Post: GoLang: Recursive Algorithm to Clone N-ary Tree
Next Post: Teaching Kids Programming - Permutation of Rooks Do Not Attack Each Other

The Permanent URL is: Egg Drop With 2 Eggs and N Floors

Leave a Reply