Very Clear Explanation by Short Examples


  • 4
    L

    Let's think in another way:
    If we get N pigs and can test T times, what is the maximum number of buckets that we can successfully detect the poison among them?


    Here we take T=1 (can only test once) and N=2 (2 pigs) as example:

        x -> not drink      o -> drink
    
    T=1  N=2:
    
       buckets       1    2    3    4
         pig 1       x    x    o    o
         pig 2       x    o    x    o
    
     Result:   2 pigs and test 1 times -> 4 buckets
    

    Conclusion T=1 N=n:

    n pigs and test 1 times can deal with how many buckets

    = 2^n


    We take T=2 (can only test twice) and N=2 (2 pigs) as example:

    T=2  N=2:
    
       buckets       1    2    3    4    5    6    7    8    9  
         pig 1       o    x    x    o    o    x    x    x    x    
         pig 2       o    o    o    x    x    x    x    x    x
                                                      
    Result:   2 pigs and test 2 times --> 9 buckets
    
    Explain:   
      pig 1 & 2 died     ->  1 possible bucket
      pig 1 died only    ->  2 possible buckets  -> 1 pig and 1 times can deal with 2 buckets(straight-forward)
      pig 2 died only    ->  2 possible buckets  -> 1 pig and 1 times can deal with 2 buckets(straight-forward)
      pig 1 & 2 survived ->  4 possible buckets  -> 2 pigs and 1 times can deal with 4 buckets(Previous case: T=1 N=2)
    

    Conclusion T=2 N=n:

    n pigs and test 2 times can deal with how many buckets

    = C(n,n) * 2^0 + C(n,n-1) * 2^1 + ... + C(n,0) * 2^n
    = (1+2)^n
    = 3^n

    Explain:
    #(all pigs died) + #(1 pigs survived) * can test 2 buckets(T=1 N=1) + #(2 pigs survived) * can test 4 buckets(T=1 N=2) + ..... + #(n pigs survived) * can test 2^n buckets(T=1 N=n)


    Now, try to think about the case T=3 (can test 3 times) and N=n (n pigs)

    Conclusion (T=3 N=n):

    n pigs and test 3 times can deal with how many buckets

    = C(n,n) * 3^0 + C(n,n-1) * 3^1 + ... + C(n,0) * 3^n
    = (1+3)^n
    = 4^n

    Explain:
    #(all pigs died) + #(1 pigs survived) * can test 3 buckets(T=2 N=1) + #(2 pigs survived) * can test 9 buckets(T=2 N=2) + ..... + #(n pigs survived) * can test 3^n buckets(T=2 N=n)


    To sum it up,

    If we get N pig and can test T times, the maximum number of buckets that we can successfully detect the poison among them is ----> (1+T)^N.

    Therefore, the answer to the question is:

     MIN(n),   where (1+T)^n >= number of buckets    
                       Note: T = minutesToTest/minutesToDie
    

Log in to reply
 

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