LeetCode 458: Poor Pigs

Problem Restatement

We are given buckets buckets of liquid.

Exactly one bucket is poisonous.

A pig dies minutesToDie minutes after drinking poison.

We have minutesToTest total minutes to determine which bucket is poisonous.

We need to return the minimum number of pigs needed to guarantee that we can identify the poisonous bucket within the time limit. The official problem asks for the minimum number of pigs needed given buckets, minutesToDie, and minutesToTest.

Input and Output

Function shape:

def poorPigs(buckets: int, minutesToDie: int, minutesToTest: int) -> int:
    ...

Examples

Example 1:

buckets = 4
minutesToDie = 15
minutesToTest = 15

There is only one testing round.

Each pig has two possible final states:

dies
survives

With two pigs, there are:

2 * 2 = 4

possible outcomes.

Those four outcomes can identify four buckets.

Answer:

2

Example 2:

buckets = 1000
minutesToDie = 15
minutesToTest = 60

We can run:

60 // 15 = 4

testing rounds.

Each pig has five possible final states:

dies after round 1
dies after round 2
dies after round 3
dies after round 4
survives all rounds

So one pig gives 5 states.

With 5 pigs:

5^5 = 3125

This is enough to distinguish 1000 buckets.

With 4 pigs:

5^4 = 625

This is not enough.

Answer:

5

First Thought: Test Buckets One by One

A direct idea is to test each bucket separately.

For example, give one bucket to one pig and wait.

If the pig dies, we found the poisoned bucket.

If the pig survives, move on to the next bucket.

This wastes too much information.

A pig does not only answer one yes-or-no question. Across multiple rounds, the time at which it dies also gives information.

Problem With Brute Force

Testing buckets one by one is too slow and uses too many pigs.

The key issue is that each pig can encode more than two outcomes when there are multiple testing rounds.

For example, if there are 4 rounds, a pig can die after round 1, 2, 3, or 4, or survive.

That gives 5 possible states.

We need to count how many buckets can be distinguished by a given number of pigs.

Key Insight

Let:

rounds = minutesToTest // minutesToDie

Each pig has:

rounds + 1

possible states.

The extra 1 is the state where the pig survives all rounds.

If each pig has states possible outcomes, then p pigs have:

states ** p

combined outcomes.

Each unique outcome can represent one bucket.

So we need the smallest p such that:

states ** p >= buckets

Why One Pig Has rounds + 1 States

Suppose:

minutesToDie = 15
minutesToTest = 60

Then:

rounds = 60 // 15 = 4

A pig can be assigned drinks in different rounds.

At the end, its final state tells us one of these:

So one pig can distinguish 5 states.

Two pigs can distinguish:

5 * 5 = 25

states.

Three pigs can distinguish:

5 * 5 * 5 = 125

states.

This is why the answer grows logarithmically.

Algorithm

Compute the number of states per pig:

states = minutesToTest // minutesToDie + 1

Then find the smallest integer pigs such that:

states ** pigs >= buckets

We can do this without floating-point logarithms.

Start with:

pigs = 0
capacity = 1

Here, capacity means how many buckets we can distinguish with the current number of pigs.

While:

capacity < buckets

add one pig:

pigs += 1
capacity *= states

Return pigs.

Walkthrough

Use:

buckets = 1000
minutesToDie = 15
minutesToTest = 60

Compute:

states = 60 // 15 + 1 = 5

Now grow capacity:

The first capacity greater than or equal to 1000 is 3125.

So the answer is:

5

Correctness

Each pig can end in exactly one of states possible outcomes: it dies after one of the available rounds, or it survives all rounds.

With p pigs, the combined outcome is a tuple of p pig states.

Therefore, p pigs can distinguish at most:

states ** p

different outcomes.

To identify one poisoned bucket among buckets possibilities, we need at least buckets distinguishable outcomes.

So any valid strategy must satisfy:

states ** p >= buckets

The algorithm starts with zero pigs and repeatedly adds one pig, multiplying the distinguishable capacity by states.

It stops at the first p where the capacity is at least buckets.

Thus, it returns the minimum number of pigs required.

Complexity

Because the constraints are small, this is effectively constant time in practice.

Implementation

class Solution:
    def poorPigs(
        self,
        buckets: int,
        minutesToDie: int,
        minutesToTest: int,
    ) -> int:
        states = minutesToTest // minutesToDie + 1

        pigs = 0
        capacity = 1

        while capacity < buckets:
            pigs += 1
            capacity *= states

        return pigs

Code Explanation

First we compute how many states one pig can represent:

states = minutesToTest // minutesToDie + 1

The division gives the number of full test rounds.

The + 1 accounts for the pig surviving all rounds.

Then:

pigs = 0
capacity = 1

With zero pigs, we can distinguish only one case.

The loop:

while capacity < buckets:

keeps adding pigs until we have enough distinguishable outcomes.

Each new pig multiplies the number of possible outcomes by states:

capacity *= states

Finally:

return pigs

returns the minimum number needed.

Alternative With Logarithms

The same idea can be written with logarithms:

import math

class Solution:
    def poorPigs(
        self,
        buckets: int,
        minutesToDie: int,
        minutesToTest: int,
    ) -> int:
        states = minutesToTest // minutesToDie + 1
        return math.ceil(math.log(buckets, states))

The loop version avoids floating-point precision issues, so it is often safer.

Testing

def run_tests():
    s = Solution()

    assert s.poorPigs(4, 15, 15) == 2
    assert s.poorPigs(4, 15, 30) == 2
    assert s.poorPigs(1000, 15, 60) == 5
    assert s.poorPigs(1, 15, 15) == 0
    assert s.poorPigs(2, 15, 15) == 1
    assert s.poorPigs(25, 15, 60) == 2
    assert s.poorPigs(26, 15, 60) == 3

    print("all tests passed")

run_tests()

Test meaning: