Poor Pigs

LeetCode #458

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.

Example:

Note

Idea:

跟绿皮书数学题老鼠测毒酒的非常类似，这个更general。

测一次能区分两个值，测两次可以区分三个值。

然后以M base的数，比要测的数大或者等于就行。一个猪测M个，N个猪测$M^N$个.

Code:

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        if(buckets==1) return 0; // if only one poisonous, no need to test

        int testN = minutesToTest/minutesToDie + 1;

        int num_pigs=1;
        int total_num = testN;
        while(total_num<buckets){
            total_num *= testN;
            num_pigs++;
        }

        return num_pigs;
    }
};