FXTi's blog
0%

poor-pigs

Posted on Edited on

Poor Pigs – LeetCode 458

Problem

Description

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

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

Follow-up:

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 “poison” bucket within p minutes? There is exact one bucket with poison.

Answer

Original

Code

1
2
3
4
5
6
class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        return ceil(log(buckets) / log(minutesToTest / minutesToDie + 1));
    }
};

思路

数学题，通过利用猪组成不同的组合，让猪一次多喝几口来尽可能多的测试水桶。于是对于猪集合{a,b,c,…}，在时间可以测试一次的情况下可以测试的桶数相当与其幂集的元素数。当能测试的次数进一步增多，相当于数组中的猪可以容纳的桶数增多，底数进一步增长，有$(时间容许测试次数+1)^{猪的个数} \geq 需要测试桶数$。时间复杂度$O(1)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$77.79\%$

Better

思路

还没看到更好的思路。