Input 1000,15, 60 expected result 5 is not correct


  • -2
    L

    4 should be the result.

    Suppose the buckets are indexed from b1 to b1000

    1. First round (4 pigs). Split buckets to 16 sub set. {b1-b64}, {b65-b128}, ...... {b961-b1000}. Then one pig die / no pig die. We can know one of the sub set contains poison.

    2. Second round (more than 3 pigs). Suppose poison in {b1-b64}, split buckets to 8 sub set. {b1-b8}, {b9-b16}, ...... {b57-b64}. Then one pig die / no pig die. We can know one of the sub set contains poison.

    3. Third round (more than 2 pigs). Suppose poison in {b1-b8}, split buckets to 4 subset. {b1-b2}, {b3-b4}, ...... {b7-b8}. Then one pig die / no pig die. We can know one of the sub set contains poison.

    4. Fourth round (more than 1 pig). Suppose poison in {b1-b2}, let the pig drink b1. If pig die, then b1 is the bucket with poison. Otherwise b2 is the bucket with poison.


  • 1
    D

    In the first step ,why you say "Then one pig die / no pig die", I don't understand. How the pigs to drink such buckets?


  • 0

    @lovedsp210 What do you mean with "more than 3 pigs"?


  • 0
    L

    @DeepInSearch @StefanPochmann

    There are 16 subset, each subset mix original 64 buckets.(1/4 from each bucket) Indexed from sb1 to sb16. Represent as binary format.
    0000,0001,0010,0011,0100,0101,0110,0111
    1000,1001,1010,1011,1100,1101,1110,1111

    There are 4 pigs.
    Let pig 1 drink all subset with ---1 format. Aka 0001, 0011, 0101, 0111, 1001, 1011, 1111
    Let pig 2 drink all subset with --1- format
    Let pig 3 drink all subset with -1-- format
    Let pig 4 drink all subset with 1--- format

    My bad. Pig could all die or all live.


  • 0
    L
    This post is deleted!

Log in to reply
 

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