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:
With 4 test rounds (60 min total, 15 min each), 5 pigs give 5^5=3125 outcomes for 1000 buckets.
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:
2Explanation:
With 2 testing rounds (40/20), each pig has 3 possible states. Two pigs distinguish 3^2 = 9 scenarios, which is enough to identify the poison among 8 buckets.
Constraints
- •
1 ≤ buckets ≤ 1000