Leetcode 458: Poor Pigs

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:

• A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
• 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.
• Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).

Problem Analysis:

Suppose the total test time is M, pig will die within m minutes after drinking, so the max time t = M / m + 1 for a pig to test buckets. Note that t = M / m + 1, not t = M / m(thinking about all pigs drinking all buckets at last, but no one died immediately, so the poison bucket is the last bucket)

We try to make pig test more buckets as possible. i.e., there are 2 pigs, and t =5. we can show a 5x5 matrix.

One pig drinks one row’s bucket water each die time, another one drinks one column’s bucket water each die time.

So we can find out the poisonous bucket in the 5 x 5 = 25 buckets. If there are 3 pigs, we can build a 5x5x5 matrix, so it can check 5 x 5 x 5 = 125 buckets. And so on.

Solution:

class Solution {
public:
  int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int times = minutesToTest / minutesToDie;
    int result = 0;
    while (pow(times + 1, result) < buckets) ++result;
    return result;
  }
};

Time Complexity: O(lgn)

Space Complexity: O(1)