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

Item	Meaning
Input	buckets, the number of buckets
Input	minutesToDie, time after which a poisoned pig dies
Input	minutesToTest, total testing time
Output	Minimum number of pigs needed
Rule	Exactly one bucket is poisonous
Goal	Identify the poisonous bucket with certainty

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:

State	Meaning
0	Survived all rounds
1	Died after round 1
2	Died after round 2
3	Died after round 3
4	Died after round 4

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:

Pigs	Capacity
0	1
1	5
2	25
3	125
4	625
5	3125

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

Metric	Value	Why
Time	O(log buckets)	Each added pig multiplies capacity by states
Space	O(1)	Only a few integers are stored

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:

Test	Why
4, 15, 15	One round, two pigs distinguish four buckets
4, 15, 30	More time still needs two pigs for four buckets
1000, 15, 60	Classic large example
1, 15, 15	One bucket needs no pigs
2, 15, 15	One pig distinguishes two buckets
25, 15, 60	Exact capacity boundary
26, 15, 60	Just above the boundary