You have k identical eggs and a building with floors numbered 1 through n. There is an unknown highest safe floor f, where 0 <= f <= n. An egg breaks when dropped above f, and survives at or below f.

A move drops one unbroken egg from a chosen floor. A broken egg cannot be reused; a surviving egg can. Future drops may depend on earlier outcomes. Return the fewest moves needed to determine f with certainty in the worst case.

Input: k = 2, n = 10

Output: 4

Explanation: Four moves are sufficient with two eggs. Start at floor 4: if it breaks, three sequential drops distinguish floors 1 through 3; if it survives, two eggs and three moves distinguish the six floors above it. Three moves can cover only six floors, so four is optimal.

Input: k = 3, n = 8

Output: 4

Explanation: With three eggs, three moves distinguish at most seven floors. Eight floors require a fourth move, even though all three eggs are initially available.

Input: k = 2, n = 4

Output: 3

Explanation: Two eggs and two moves distinguish only three floors. For four floors, use three moves; for example, first test floor 2 and budget for both outcomes.

215. Super Egg Drop

Hard•

Example 1:

Input: k = 2, n = 10

Output: 4

Example 2:

Input: k = 3, n = 8

Output: 4

Explanation: With three eggs, three moves distinguish at most seven floors. Eight floors require a fourth move, even though all three eggs are initially available.

Example 3:

Input: k = 2, n = 4

Output: 3

Explanation: Two eggs and two moves distinguish only three floors. For four floors, use three moves; for example, first test floor 2 and budget for both outcomes.

Constraints

1 <= k <= 100
1 <= n <= 10000

Accepted4/5|Acceptance Rate80.0%