Poor Pigs
HardMathDynamic ProgrammingCombinatorics
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