Description
You have k identical eggs and n floors. Find the minimum number of moves needed to determine with certainty what the critical floor f is (the minimum floor from which an egg breaks when dropped).
Examples
Input:
k = 2, n = 6Output:
3Explanation:
With 2 eggs and 6 floors, minimum 3 moves needed.
Input:
k = 1, n = 10Output:
10Explanation:
With only 1 egg and 10 floors, a linear search strategy starting from floor 1 is required. In the worst case, the critical floor is floor 10, requiring testing floors 1, 2, 3, ..., 10 sequentially. This takes 10 moves.
Input:
k = 4, n = 8Output:
4Explanation:
With 4 eggs and 8 floors, an efficient binary-search-like strategy works. Starting by dropping from floor 4: if it breaks, 3 eggs remain for floors 1-3 (at most 3 moves). If it does not break, floor 6 is tested next. This strategy guarantees finding the critical floor in 4 moves.
Constraints
- •
1 ≤ k ≤ 100 - •
1 ≤ n ≤ 10⁴