# Poor Pigs
**Difficulty:** HARD
[External](https://leetcode.com/problems/poor-pigs)
Canonical: https://scaleengineer.com/dsa/problems/poor-pigs
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
---
## Problem
There are `buckets` buckets of liquid, where **exactly one** of the buckets is poisonous. To figure out which one is poisonous, you feed some number of (poor) pigs the liquid to see whether they will die or not. Unfortunately, you only have `minutesToTest` minutes to determine which bucket is poisonous.

You can feed the pigs according to these steps:

1. Choose some live pigs to feed.
2. For each pig, choose which buckets to feed it. The pig will consume all the chosen buckets simultaneously and will take no time. Each pig can feed from any number of buckets, and each bucket can be fed from by any number of pigs.
3. Wait for `minutesToDie` minutes. You may **not** feed any other pigs during this time.
4. After `minutesToDie` minutes have passed, any pigs that have been fed the poisonous bucket will die, and all others will survive.
5. Repeat this process until you run out of time.

Given `buckets`, `minutesToDie`, and `minutesToTest`, return _the **minimum** number of pigs needed to figure out which bucket is poisonous within the allotted time_.

**Example 1:**

**Input:** buckets = 4, minutesToDie = 15, minutesToTest = 15
**Output:** 2
**Explanation:** We can determine the poisonous bucket as follows:
At time 0, feed the first pig buckets 1 and 2, and feed the second pig buckets 2 and 3.
At time 15, there are 4 possible outcomes:
- If only the first pig dies, then bucket 1 must be poisonous.
- If only the second pig dies, then bucket 3 must be poisonous.
- If both pigs die, then bucket 2 must be poisonous.
- If neither pig dies, then bucket 4 must be poisonous.

**Example 2:**

**Input:** buckets = 4, minutesToDie = 15, minutesToTest = 30
**Output:** 2
**Explanation:** We can determine the poisonous bucket as follows:
At time 0, feed the first pig bucket 1, and feed the second pig bucket 2.
At time 15, there are 2 possible outcomes:
- If either pig dies, then the poisonous bucket is the one it was fed.
- If neither pig dies, then feed the first pig bucket 3, and feed the second pig bucket 4.
At time 30, one of the two pigs must die, and the poisonous bucket is the one it was fed.

**Constraints:**

* `1 <= buckets <= 1000`
* `1 <= minutesToDie <= minutesToTest <= 100`

# Approaches
## Iterative Approach
This approach directly simulates the process of adding pigs one by one and checking if they are sufficient. We know that with `p` pigs and `T+1` possible states for each pig (where `T` is the number of tests), we can distinguish between `(T+1)^p` outcomes. We start with 0 pigs and keep adding one pig at a time, calculating the total number of distinguishable states. We stop when this number is greater than or equal to the number of buckets.
**Time:** O(log_states(buckets)). The number of iterations is the smallest `p` such that `states^p >= buckets`. This is logarithmic with respect to `buckets`. · **Space:** O(1). We only use a few variables to store the state.
**Pros:** Easy to understand and implement.; Avoids floating-point arithmetic, eliminating potential precision errors.
**Cons:** Slightly slower than the direct mathematical formula, although the performance difference is negligible for the given constraints.
### Explanation
First, calculate the number of states a single pig can represent. A pig can die after any of the possible test rounds, or it can survive all of them. The number of test rounds is `minutesToTest / minutesToDie`. So, a pig can be in one of `(minutesToTest / minutesToDie) + 1` states. Let's call this `states_per_pig`.

We need to find the minimum number of pigs, `p`, such that `(states_per_pig)^p >= buckets`.

We can solve this by starting with `p = 0` and iteratively increasing `p` until the condition is met. We use a variable, say `max_buckets`, initialized to 1 (representing the case with 0 pigs). In each iteration, we multiply `max_buckets` by `states_per_pig` and increment our pig count. We continue this until `max_buckets` is at least as large as the given `buckets`.

The final pig count is our answer. This method avoids using floating-point arithmetic.

```java
class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        if (buckets == 1) {
            return 0;
        }
        int states = minutesToTest / minutesToDie + 1;
        int pigs = 0;
        long maxBuckets = 1;
        while (maxBuckets < buckets) {
            maxBuckets *= states;
            pigs++;
        }
        return pigs;
    }
}
```
### Algorithm
1. Calculate `states = (minutesToTest / minutesToDie) + 1`.
2. Initialize `pigs = 0` and `max_buckets_covered = 1`.
3. Start a loop that continues as long as `max_buckets_covered < buckets`.
4. Inside the loop, increment `pigs` by 1.
5. Update `max_buckets_covered` by multiplying it with `states`.
6. Once the loop terminates, return `pigs`.

## Mathematical Approach using Logarithms
This approach leverages a mathematical formula derived from the problem's core logic. The problem can be framed as finding the number of digits required to represent `buckets` unique items in a base-`k` number system. Here, the base `k` is the number of outcomes a single pig can distinguish, which is `(minutesToTest / minutesToDie) + 1`.
**Time:** O(1). The calculation involves a few arithmetic operations and calls to `log` and `ceil`, which are considered constant time. · **Space:** O(1). No extra space proportional to the input size is used.
**Pros:** Most efficient solution with constant time complexity.; Provides a direct and concise calculation.
**Cons:** Relies on floating-point arithmetic, which can be prone to precision issues in some programming environments or with different constraints, although standard libraries are generally reliable.; The derivation of the formula is less intuitive than the iterative simulation.
### Explanation
The fundamental insight is that each pig is an independent source of information. The number of distinct outcomes for one pig is `states = (minutesToTest / minutesToDie) + 1`. This is because a pig can die in any of the `minutesToTest / minutesToDie` test intervals, or it can survive, giving `(minutesToTest / minutesToDie) + 1` possibilities.

With `p` pigs, the total number of combined outcomes we can distinguish is `states^p`.

To identify the single poisonous bucket out of `buckets` possibilities, we need the number of distinguishable outcomes to be at least equal to the number of buckets. This gives us the inequality: `states^p >= buckets`.

To solve for `p`, we can use logarithms. Taking the logarithm of both sides (e.g., natural log):
`log(states^p) >= log(buckets)`
`p * log(states) >= log(buckets)`
`p >= log(buckets) / log(states)`

Since the number of pigs `p` must be an integer, we need the smallest integer `p` that satisfies this condition, which is the ceiling of the expression on the right.
`p = ceil(log(buckets) / log(states))`

This formula directly calculates the result.

```java
class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int states = minutesToTest / minutesToDie + 1;
        // We need to solve for p in: states^p >= buckets
        // p >= log(buckets) / log(states)
        // p = ceil(log_states(buckets))
        double p_double = Math.log(buckets) / Math.log(states);
        return (int) Math.ceil(p_double);
    }
}
```
### Algorithm
1. Calculate `states = (minutesToTest / minutesToDie) + 1`.
2. Calculate the required number of pigs `p` using the formula `p = log(buckets) / log(states)`. Note that `log_states(buckets) = log(buckets) / log(states)`.
3. Since the number of pigs must be an integer, take the ceiling of the result from the previous step.
4. Return the final integer value.

# Solutions
### Java

```java
class Solution {
public
  int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int base = minutesToTest / minutesToDie + 1;
    int res = 0;
    for (int p = 1; p < buckets; p *= base) {
      ++res;
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int base = minutesToTest / minutesToDie + 1;
    int res = 0;
    for (int p = 1; p < buckets; p *= base)
      ++res;
    return res;
  }
};

```

### Python

```python
class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int: base = minutesToTest // minutesToDie + 1 res, p = 0, 1 while p < buckets: p *= base res += 1 return res

```