458. Poor Pigs #
Problem #
There are buckets buckets of liquid, where exactly one of the buckets is poisonous. To figure out which one is poisonous, you feed some number of (poor) pigs the liquid to see whether they will die or not. Unfortunately, you only have minutesToTest minutes to determine which bucket is poisonous.
You can feed the pigs according to these steps:
- Choose some live pigs to feed.
- For each pig, choose which buckets to feed it. The pig will consume all the chosen buckets simultaneously and will take no time.
- Wait for minutesToDie minutes. You may not feed any other pigs during this time.
- After minutesToDie minutes have passed, any pigs that have been fed the poisonous bucket will die, and all others will survive.
- Repeat this process until you run out of time.
Given buckets, minutesToDie, and minutesToTest, return the minimum number of pigs needed to figure out which bucket is poisonous within the allotted time.
Example 1:
Input: buckets = 1000, minutesToDie = 15, minutesToTest = 60
Output: 5
Example 2:
Input: buckets = 4, minutesToDie = 15, minutesToTest = 15
Output: 2
Example 3:
Input: buckets = 4, minutesToDie = 15, minutesToTest = 30
Output: 2
Constraints:
- 1 <= buckets <= 1000
- 1 <= minutesToDie <= minutesToTest <= 100
Problem Summary #
There are buckets buckets of liquid, where exactly one bucket contains poison, and the rest contain water. They all look the same from the outside. To figure out which bucket contains poison, you can feed some pigs and determine it by observing whether the pigs die. Unfortunately, you only have minutesToTest minutes to determine which bucket of liquid is poisonous.
The rules for feeding pigs are as follows:
- Choose several live pigs to feed
- You may allow a pig to drink from any number of buckets simultaneously, and this process takes no time.
- After a pig drinks the liquid, there must be a cooldown period of minutesToDie minutes. During this period, you can only observe and are not allowed to continue feeding pigs.
- After minutesToDie minutes have passed, all pigs that drank the poison will die, and all other pigs will survive.
- Repeat this process until time runs out.
Given the number of buckets, buckets, minutesToDie, and minutesToTest, return the minimum number of pigs needed to determine which bucket is poisonous within the allotted time.
Solution Approach #
Use a mathematical method. Taking minutesToDie=15, minutesToTest=60, and 1 pig as an example, it can test 5 buckets.
- 0-15 The pig drinks the liquid from the first bucket. If it dies, then the first bucket is poisonous; otherwise continue testing
- 15-30 The pig drinks the liquid from the second bucket. If it dies, then the second bucket is poisonous; otherwise continue testing
- 30-45 The pig drinks the liquid from the third bucket. If it dies, then the third bucket is poisonous; otherwise continue testing
- 45-60 The pig drinks the liquid from the fourth bucket. If it dies, then the fourth bucket is poisonous
- If the pig does not die in the end, then the fifth bucket is poisonous
So when minutesToDie and minutesToTest are fixed, one pig can determine at most base = minutesToTest / minutesToDie + 1 buckets
Assume the number of pigs is num, then pow(base, num) >= buckets. According to the rules of logarithms, taking logarithms on both sides gives: num >= Log10(buckets) / Log10(base)
Code #
package leetcode
import "math"
func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
base := minutesToTest/minutesToDie + 1
return int(math.Ceil(math.Log10(float64(buckets)) / math.Log10(float64(base))))
}
中文