Description
Given buckets of liquid, one is poison. Pigs die after minutesToDie if they drink poison. You have minutesToTest time. Find minimum pigs needed to find poison.
Examples
Input:
buckets = 1000, minutesToDie = 15, minutesToTest = 60Output:
5Explanation:
5 pigs needed.
Input:
buckets = 1, minutesToDie = 10, minutesToTest = 20Output:
0Explanation:
With only 1 bucket, no pigs are needed since there is only one possible bucket containing poison. The answer is trivially 0.
Input:
buckets = 8, minutesToDie = 20, minutesToTest = 40Output:
3Explanation:
With 2 testing rounds (40/20), each pig has 3 possible states. Three pigs distinguish 3^3 = 27 scenarios, enough to identify the poison among 8 buckets.
Constraints
- •
1 ≤ buckets ≤ 1000