Incorrect Run Code/Solution? [Fixed]


  • 1
    I

    I believe that the run code is incorrect for 4, 1, 2 (buckets, minutes to die, minutes to test respectively) and perhaps others as well.

    Suppose that we are trying to find the bucket containing poison out of four with two "attempts". Obviously we will have to check at least three of the four buckets to determine which one has poison, so for at least one "attempt" we will have to check two buckets at once with the single pig. However, if the pig dies we have no way to figure out which bucket actually contained poison and which contained water.

    I think the answer should be the smallest n such that pow(2,n)>(buckets-1)/(minutesToTest/minutesToDie).
    In the case listed above the answer would be 2.

    Am I missing anything?


  • 0
    P
    This post is deleted!

  • 0
    I

    I meant that if two or more buckets were tested at once and the pig died (in the test case mentioned above), we would have no way to determined the poisoned bucket without additional pigs.
    However, if we were to test the buckets one by one, we would need to test three buckets out of the four and use three "attempts" when the run code case says that we only need two.
    Could you give an example of a process that would work for the case above?


  • -1
    P
    This post is deleted!

  • 0
    Y

    @inferee You are right. We need at least two pigs for the case. I'll update the test cases.


  • 0
    Y

    @inferee Updated! Would you please try it again? Thank you!


  • -1
    I

    The run code appears to be correct.
    I got my solution as follows:

    We can split the buckets into minutesToTest/minutesToDie groups, first of all.
    For each group, we can test for up to 2^n-1 buckets given n pigs EXCEPT for the last bucket.
    Each bucket can be assigned a unique combination of pigs (like binary). For example, given 3 pigs bucket 0 would be assigned to 000, bucket 1 001, all the way to bucket 7 which would be 111.
    However if there were 2^n buckets then one bucket would correspond to none of the pigs being poisoned (or all zeros in binary), which we would be unable to tell apart from when that group of buckets doesn't contain the poison.
    Because of this, we can only test for 2^n-1 instead of 2^n buckets for all groups except the last.
    We then find the smallest n that satisfies the condition.

    My code is below:

            if (buckets==1){
                return 0;
            }
            int bucketsInGroup=(buckets-1)/(minutesToTest/minutesToDie)+1;
            int count=0;
            while (bucketsInGroup>0){
                bucketsInGroup=bucketsInGroup>>>1;
                count++;
            }
            return count;
    

  • 0
    Y

    @inferee said in Incorrect Run Code/Solution?:
    It's a typo I guess.

    while (result>0){

    Should be:

    while (bucketsInGroup>0){
    

  • 0
    Y

    @inferee By the way, for the special case that with only one bucket, it's with poison by default. So, return 0 for that case.

    (The question is asked this way. But I think, it should be "there is at most one bucket with poison". Then for the special case it would return 1, as you did.)


  • 0
    I

    You are correct but there seems to be a better method as mentioned as lano1 in another topic. His idea was to use different bases other than two based on the number of "attempts".


Log in to reply
 

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