A lab wants the highest floor of a floors-storey tower from which a phone survives a drop. There is some unknown threshold floor f (0 <= f <= floors): drops from floors <= f never break a phone, drops from higher floors always do. A broken phone cannot be reused, an intact one can. With phones identical phones, return the smallest number of drops that guarantees finding f in the worst case.
Examples
Input: phones = 1, floors = 5
Output: 5
Explanation: with one phone you must try floors 1, 2, 3, ... in order.
Input: phones = 2, floors = 10
Output: 4
Constraints
1 <= phones <= 1000 <= floors <= 10**5- A table over (phones, floors) with a loop over the next drop floor is O(phones * floors**2), far too slow; find a faster formulation.
Goals
- Reverse the question: how many floors can t tests with e phones settle?
- Derive a recurrence from the two outcomes of one drop