Brief explanation of the solution:


  • 0
    L

    'Within' 15 minutes means the pig can die any time within that time.

    in 60 min timeframe, we have 4 slots of 15 mins each. Now that means there are 5 states at the end of 60 mins as follows:

    1. Pig dies within 00 - 15 mins
    2. Pig dies within 15 - 30 mins
    3. Pig dies within 30 - 45 mins
    4. Pig dies within 45 - 60 mins
    5. Pig is Alive

    Now, each pig can be used to detect 5 events.

    let's number pigs as 0, 1, 2, .... x-1

    Assume, that we need to create some kind of unique encoding for 1000 buckets using 5 digits (i.e. base 5) since we have 5 states. We can use base 5 number system like 00, 01, 02, 03, 04, 10, 11, 12, 13, 14, 20 , 21 ...

    Now, at time t = 0, make pig0 drink the buckets with 0 as the last digit, pig1 drink second last digit as 0 and so on... take the note about the result at the end

    at time t = 15 min, make pig0 drink the buckets with 1 as the last digit, pig1 drink second last digit as 1 and so on... take the note about the result at the end. Remember if any pig died in the first case, we know the ping number is nothing but the encoded digit of the bucket which further reduces our scope and helps in convergence.

    Hence, going by this logic, we should be able to find our the number of pigsfor 1000 buckets and 15/60 min time. We have 5 states for each pug experiment and hence need ceil(log(1000)/log(5)) pigs

    in a generic case, the ans would be as follows:

    numOfStates = minutesToTest / minutesToDie + 1
    return int(math.ceil(math.log(buckets)/math.log(numOfStates)))

    Example:

    Assume we have 125 buckets.
    We will number them from 000 to 444.
    Assume 123 numbered bucket has poison (123)base5 = 38

    how will we detect the above bucket.

    For this case, pig2 will die within 15-30 mins since it would have had poison from 123. That gives us the 3rd digit from last is 1.
    pig1 will die within 30-45 mins since it would have had poison from 123. That gives us the 2nd digit from last is 2.
    pig3 will die within 45-60 mins since it would have had poison from 123. That gives us the last digit is 3.

    Hence we know the bucket!


Log in to reply
 

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