Java Explained 1ms Solution

• ``````public class Solution {
public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
buckets--;
int base=minutesToTest/minutesToDie+1;
int count=0;
while (buckets>0){
buckets/=base;
count++;
}
return count;
}
}
``````

We have minutesToTest/minutesToDie "attempts" that are possible in the time span, so there are minutesToTest/minutesToDie+1 possible results for each pig: death on first attempt, death on second attempt ... death on last attempt, and life. Let the number of possible results be "base".
The problem then becomes finding the smallest n such that pow(base,n)>=buckets, which should be relatively simple.
An example:
(7,3,10), poison at 5.
base=10/3=3
number of pigs=2
pig 0 will check all numbers that are NX (base 3) on attempt N
pig 1 will check all numbers that are XN (base 3) on attempt N
attempt 0
pig 0 checks 0,1,2
pig 1 checks 0,3,6
attempt 1
pig 0 checks 3,4,5 dies here (so the number is 1X base 3)
pig 1 checks 1,4,7
attempt 2
pig 1 checks 2,5,8 dies here (so the number is X2 base 3)
(buckets 7 and 8 do not exist for this case)
Therefore 12 base 3 is poisoned, or 5 base 10.

• I think it maybe a little bit easier to understand if you replace the

``````   if(buckets-- == 1) return 0;
``````

by simply

``````  buckets--;
``````

and it should be the same result, as we can remove one bucket from the collection and test whether the remaining buckets have the poison or not.

• How about poorPigs(3, 2, 1), I think it should return 2.

• How about poorPigs(3, 2, 1), I think it should return 3.

In that case I think you cannot tell it at all. Since no matter how many pigs do you have they will only show signs of poison after 2 minutes which exceeds the time limit 1

• This post is deleted!

• @shallpion Sorry, I was wrong. I thought the pigs would die immediately and revive after minutesToDie.

• I'm confused by this question. Can one pig check as many bucket as we want at a specific time?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.