Java Explained 1ms Solution


  • -1
    I
    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.


  • 1
    S

    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.


  • 0
    T

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


  • 0
    S

    @tju_xu said in Java Explained 1ms Solution:

    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


  • 0
    T
    This post is deleted!

  • 0
    T

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


  • 0
    B

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


Log in to reply
 

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