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) —
loading...
Last Post: GoLang: Recursive Algorithm to Clone N-ary Tree
Next Post: Teaching Kids Programming - Permutation of Rooks Do Not Attack Each Other