#887
Super Egg Drop
international master · 1975 · lc hard +32 · verified · 29.9% accepted · 3,821 likes · top 7%
Description
You have k identical eggs and access to a building with n floors labeled 1 through n.
There exists a critical floor f (with 0 <= f <= n) such that dropping an egg from any floor above f breaks it, while dropping from floor f or below does not. Broken eggs cannot be reused; unbroken eggs can.
Each move consists of dropping an unbroken egg from any chosen floor between 1 and n.
Return the minimum number of moves guaranteed to determine the exact value of f.
Example 1:
Input: k = 1, n = 2
Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know that f = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
If it does not break, then we know f = 2.
Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
Example 2:
Input: k = 2, n = 6
Output: 3
Example 3:
Input: k = 3, n = 14
Output: 4
Code
1
2
3