Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/458.html

458. Poor Pigs

Level

Hard

Description

There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?

Answer this question, and write an algorithm for the general case.

General case:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the poisonous bucket within p minutes? There is exactly one bucket with poison.

Note:

  1. A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
  2. After a pig has instantly finished drinking buckets, there has to be a cool down time of m minutes. During this time, only observation is allowed and no feedings at all.
  3. Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).

Solution

This problem is difficult to solve directly, but if starting with simplest cases, the problem can be solved gradually.

Suppose there is only one pig, and drinking the poison will make the pig die within 15 minutes, what is the maximum number of buckets that can be figured out within one hour, given that only one bucket is poisonous?

Since one hour equals 60 minutes, it can be calculated that 60 / 15 = 4, so one pig can drink 4 buckets of drinks and be observed. If the pig dies at the time point of 15 minutes, 30 minutes, 45 minutes or 60 minutes, then it can be seen that the 1st bucket, the 2nd bucket, the 3rd bucket or the 4th bucket is poisonous, respectively. So 4 buckets can be figured out within one hour. However, actually 5 buckets can be figured out within one hour. Suppose there are 5 buckets. If the pig doesn’t die after drinking the first 4 buckets of drinks, then none of the first 4 buckets is poisonous and thus the 5th bucket is poisonous.

If the number of pigs increases to 2, and drinking the poison will make the pig die within 15 minutes, then what is the maximum number of buckets that can be figured out within one hour, given that only one bucket is poisonous?

The answer is 52 = 25. Put the 25 buckets in 5 rows and 5 columns. Each time, the first pig drinks 5 buckets of drinks in one row, and the second pig drinks 5 buckets of drinks in one column. Check the time when each of the two pigs die, and the row and the column of the poisonous bucket can be determined.

If the number of pigs is x, with other conditions unchanged, then the maximum number of buckets that can be figured out is 5x. If there are 1000 buckets, the minimum amount of pigs is 5 since 54 = 625 < 1000 and 55 = 3125 > 1000.

For the general case, each pig can drink p / m times and be observed. (each time a pig can drink any number of buckets of drinks), so one pig can figure out side = p / m + 1 buckets within the given time. To find the minimum number of pigs, find the minimum x such that Math.pow(side, x) >= n.

  • class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int side = minutesToTest / minutesToDie + 1;
        int min = (int) Math.ceil(Math.log(buckets) / Math.log(side));
        return min;
    }
}

  • class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        base = minutesToTest // minutesToDie + 1
        res, p = 0, 1
        while p < buckets:
            p *= base
            res += 1
        return res

############

class Solution(object):
    def poorPigs(self, buckets, minutesToDie, minutesToTest):
        """
        :type buckets: int
        :type minutesToDie: int
        :type minutesToTest: int
        :rtype: int
        """
        tests = minutesToTest / minutesToDie + 1
        pigs = 0
        while tests ** pigs < buckets:
            pigs += 1
        return pigs

  • class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int base = minutesToTest / minutesToDie + 1;
        int res = 0;
        for (int p = 1; p < buckets; p *= base) ++res;
        return res;
    }
};

  • func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
	base := minutesToTest/minutesToDie + 1
	res := 0
	for p := 1; p < buckets; p *= base {
		res++
	}
	return res
}

All Problems

All Solutions