Solution with explanation of information theory.


  • 0
    Z

    Using the information theory, we needn't to know which pig needs to drink which bucket, the only thing we need to do is get enough information to make sure the bucket is the poison bucket.

    First, according to the information theory, if we want to know which bucket is poison, we should have information at least:
    poisonInfo = Math.log(buckets, 2)

    For one pig, the attempts of it is:
    t = minutesToTest // minutesToDie

    That's mean, we can do t attempts to a pig.
    But, we can only have t+1 results of the t attempts, because that the pig can only die one time.
    The pig didn't die, died at the first attempt, died at the second attempt.....
    So, the ammound of information we can get the from this pig is:
    pigInfo = math.log(t + 1, 2)

    So, we need n pigs to get the information which needs to be bigger than the poisonInfo, the result is:
    n = int(math.ceil(posionInfo / pigInfo))

    So the code is:

        def poorPigs(self, buckets, minutesToDie, minutesToTest):
            #the information of the posion bucket
            posionInfo = math.log(buckets, 2)
            #the information that we can get from a pig
            pigInfo = math.log(minutesToTest // minutesToDie + 1, 2)
            #so,the result..
            return int(math.ceil(posionInfo / pigInfo))
    

Log in to reply
 

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