# 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:

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

## Examples

Example 1:

```python
buckets = 4
minutesToDie = 15
minutesToTest = 15
```

There is only one testing round.

Each pig has two possible final states:

```python
dies
survives
```

With two pigs, there are:

```python
2 * 2 = 4
```

possible outcomes.

Those four outcomes can identify four buckets.

Answer:

```python
2
```

Example 2:

```python
buckets = 1000
minutesToDie = 15
minutesToTest = 60
```

We can run:

```python
60 // 15 = 4
```

testing rounds.

Each pig has five possible final states:

```python
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:

```python
5^5 = 3125
```

This is enough to distinguish `1000` buckets.

With `4` pigs:

```python
5^4 = 625
```

This is not enough.

Answer:

```python
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:

```python
rounds = minutesToTest // minutesToDie
```

Each pig has:

```python
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:

```python
states ** p
```

combined outcomes.

Each unique outcome can represent one bucket.

So we need the smallest `p` such that:

```python
states ** p >= buckets
```

## Why One Pig Has `rounds + 1` States

Suppose:

```python
minutesToDie = 15
minutesToTest = 60
```

Then:

```python
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:

```python
5 * 5 = 25
```

states.

Three pigs can distinguish:

```python
5 * 5 * 5 = 125
```

states.

This is why the answer grows logarithmically.

## Algorithm

Compute the number of states per pig:

```python
states = minutesToTest // minutesToDie + 1
```

Then find the smallest integer `pigs` such that:

```python
states ** pigs >= buckets
```

We can do this without floating-point logarithms.

Start with:

```python
pigs = 0
capacity = 1
```

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

While:

```python
capacity < buckets
```

add one pig:

```python
pigs += 1
capacity *= states
```

Return `pigs`.

## Walkthrough

Use:

```python
buckets = 1000
minutesToDie = 15
minutesToTest = 60
```

Compute:

```python
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:

```python
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:

```python
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:

```python
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

```python
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:

```python
states = minutesToTest // minutesToDie + 1
```

The division gives the number of full test rounds.

The `+ 1` accounts for the pig surviving all rounds.

Then:

```python
pigs = 0
capacity = 1
```

With zero pigs, we can distinguish only one case.

The loop:

```python
while capacity < buckets:
```

keeps adding pigs until we have enough distinguishable outcomes.

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

```python
capacity *= states
```

Finally:

```python
return pigs
```

returns the minimum number needed.

## Alternative With Logarithms

The same idea can be written with logarithms:

```python
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

```python
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 |