Can be done with 8 pigs using bit equivalents of the bucket numbers.


  • 0
    S

    1000 buckets
    8 pigs
    Up to 15 minutes for the poison to act.

    In the first 15 minutes, convert the first 250 buckets into their corresponding binary equivalents, and feed the pigs in that order. For example, the binary equivalent of bucket 1 is 00000001, therefore only pig 1 drinks the bucket. Next, the binary equivalent of bucket 2 is 00000010, therefore only pig 2 drinks the bucket. The same way, the binary equivalent of bucket 250 is 11111010, therefore pigs 8, 7, 6, 5, 4 and 2 drink from this bucket.
    At the end of 15 minutes, look for the pigs that die. Convert the binary number into a decimal number to find the poisoned bucket.

    If none of the pigs dies, take the next 250 buckets, and repeat the process with the same 8 pigs. Within 1 hour, you should have found the poisoned bucket in the 1000 total buckets.


Log in to reply
 

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