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.
What is 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 Explanation: One optimal strategy is:
Regardless of the outcome, it takes at most 14 drops to determine f.
You are given two identical eggs and a building with n
floors labeled from 1 to n
. There exists a floor f
(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. You want to determine the minimum number of moves needed to find f
with certainty.
The simplest approach is to perform a linear search. Drop the first egg from floor 1, then floor 2, and so on. If the egg breaks at floor x
, then f = x - 1
. If the egg doesn't break until floor n
, then f = n
. However, this approach doesn't leverage the fact that you have two eggs and won't result in an optimal solution.
We can solve this problem using dynamic programming. Let dp[i][j]
be the minimum number of moves needed to determine f
with i
eggs and j
floors.
Base Cases:
dp[1][j] = j
: With one egg, we must try each floor sequentially.dp[i][0] = 0
: If there are no floors, no moves are needed.dp[i][1] = 1
: If there is one floor, one move is needed.Recursive Relation:
For each floor x
(1 <= x <= j), we have two possibilities:
i - 1
eggs and x - 1
floors to check. The number of moves in this case is dp[i - 1][x - 1] + 1
.i
eggs and j - x
floors to check. The number of moves in this case is dp[i][j - x] + 1
.We want to minimize the worst-case scenario, so we take the maximum of these two possibilities for each x
and then minimize over all x
:
dp[i][j] = min(max(dp[i - 1][x - 1], dp[i][j - x]) + 1)
for all 1 <= x <= j
Edge Cases:
n = 1
: Return 1.n = 0
: Return 0.Code Implementation (Python):
def egg_drop(n: int) -> int:
dp = [[0] * (n + 1) for _ in range(3)] # Only need to store 2 rows
for j in range(1, n + 1):
dp[1][j] = j
for i in range(2, 3):
for j in range(1, n + 1):
dp[i][j] = float('inf')
for x in range(1, j + 1):
dp[i][j] = min(dp[i][j], max(dp[i - 1][x - 1], dp[i][j - x]) + 1)
return dp[2][n]
# Example usage
n = 100
result = egg_drop(n)
print(f"Minimum number of moves for n={n}: {result}")
It is also possible to use a mathematical approach, but that is not generally expected in an interview. For k
drops and e
eggs, the number of floors that can be checked in worst case is C(k, 1) + C(k, 2) + .... + C(k, e)
where C(n,r) represents the binomial coefficient "n choose r". Therefore, we need to find the smallest k
for which the above expression is n
or larger.