Solution with 8 pigs for 1000: Includes abstracted solution


  • 0
    C

    The solution to this problem is due to log_6(1000) = 2.5... The algorithm is as such:

    • Divide 1000 by 6 which is approximately 167. Take 6 pigs and make them drink from 167 buckets each. It is okay to have one overlapping buckets because then we will find the poison bucket immediately.
    • Take the subarray of buckets one of the 6 pigs died from. The poison bucket must be within that subarray. Take the 5 pigs that survived and add one more, divide that subarray into 6 more equal divisions.
    • Continue this pattern. You will be able to find the poison bucket with 8 pigs.
      1000 -> 6 Pigs -> 167 (One dies) , 15 minutes used
      166 -> 7 Pigs -> 28 (One dies) , 30 minutes used
      28 -> 8 Pigs -> 5 (One dies) , 45 minutes used (No need to add another pig)
      5 -> 8 Pigs -> 1 (One dies) found bucket

    Abstract solution: If we are given N time to find one poisonous bucket in M buckets and each pig dies in T amount of time. We know we have time for N/T samples. We need to find the solution to this equation:

    log_x(M) = N/T (find x)

    The total number of pigs needed will be x + (N/T - 1) pigs.


Log in to reply
 

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