Poor Pigs

Problem#

You have buckets buckets, one of which is poisoned. A pig that drinks from a bucket dies after minutesToDie minutes. Within minutesToTest minutes, find the minimum number of pigs needed to identify the poison bucket.

Examples#

buckets=4, minutesToDie=15, minutesToTest=15 → 2.
buckets=1000, minutesToDie=15, minutesToTest=60 → 5.

Constraints#

1 <= buckets <= 1000, 1 <= minutesToDie <= minutesToTest <= 100.

Approach#

Let rounds = minutesToTest / minutesToDie. Each pig contributes one base-(rounds+1) digit of information (state: dies in round 1, round 2, …, or survives). With p pigs, you can distinguish (rounds + 1)^p buckets. Find smallest p with (rounds + 1)^p >= buckets.

Solution#

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int rounds = minutesToTest / minutesToDie + 1; // states per pig
        int pigs = 0;
        long long power = 1;
        while (power < buckets) {
            power *= rounds;
            ++pigs;
        }
        return pigs;
    }
};

func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
    rounds := minutesToTest/minutesToDie + 1
    pigs := 0
    power := 1
    for power < buckets {
        power *= rounds
        pigs++
    }
    return pigs
}

class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        rounds = minutesToTest // minutesToDie + 1
        pigs = 0
        power = 1
        while power < buckets:
            power *= rounds
            pigs += 1
        return pigs

function poorPigs(buckets, minutesToDie, minutesToTest) {
    const rounds = Math.floor(minutesToTest / minutesToDie) + 1;
    let pigs = 0;
    let power = 1;
    while (power < buckets) {
        power *= rounds;
        pigs++;
    }
    return pigs;
}

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int rounds = minutesToTest / minutesToDie + 1;
        int pigs = 0;
        long power = 1;
        while (power < buckets) {
            power *= rounds;
            pigs++;
        }
        return pigs;
    }
}

function poorPigs(buckets: number, minutesToDie: number, minutesToTest: number): number {
    const rounds = Math.floor(minutesToTest / minutesToDie) + 1;
    let pigs = 0;
    let power = 1;
    while (power < buckets) {
        power *= rounds;
        pigs++;
    }
    return pigs;
}

Editorial#

The construction matches the information-theoretic lower bound: arrange buckets as a (rounds+1)-dimensional hypercube and have pig i drink from a fixed slab on dimension i in each round. The pig’s death-round encodes its slab’s index, recovering the bucket coordinate.

Complexity#

Time: O(log buckets).
Space: O(1).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#