Prototype Drop Tests

Hard

A lab wants to know how high a new gadget can fall from and survive. You have prototypes identical prototypes and a building with floors numbered 1 to floors. There is a threshold f (0 ≤ f ≤ floors): a prototype dropped from any floor above f breaks, while one dropped from floor f or lower stays intact. You don't know f in advance. In one drop you release an intact prototype from any floor between 1 and floors. A broken prototype is gone for good; one that survives can be dropped again. Return the smallest number of drops that is guaranteed to pin down f exactly, whatever its value.

Example 1

prototypes=1, floors=3 → 3

With one prototype there is no room for risk: drop it from floors 1, 2 and 3 in turn. The worst case needs 3 drops.

Example 2

prototypes=2, floors=10 → 4

Drop first from floor 4. If it breaks, the second prototype checks floors 1–3 one by one. If not, drop next from floor 7, then 9. Every outcome is settled within 4 drops.

Example 3

prototypes=3, floors=1 → 1

Constraints

1 ≤ prototypes ≤ 100
1 ≤ floors ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Binary Search Dynamic Programming