458. Poor Pigs - Solution & Explanation

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

Choose some live pigs to feed.
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.
Wait for minutesToDie minutes. You may not feed any other pigs during this time.
After minutesToDie minutes have passed, any pigs that have been fed the poisonous bucket will die, and all others will survive.
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

Approach overview

Problem Overview: You have buckets buckets where exactly one is poisoned. A pig dies minutesToDie minutes after drinking poison, and you have minutesToTest minutes total. Multiple rounds of testing are possible. The task is to compute the minimum number of pigs required to guarantee identifying the poisoned bucket.

Approach 1: Binary Strategy (O(log n) time, O(1) space)

This approach treats each pig as a binary indicator across testing rounds. If a pig drinks from a bucket and dies during a specific round, that timing encodes information about which bucket was poisoned. With r = minutesToTest / minutesToDie rounds, each pig effectively contributes a bit across multiple time intervals. By assigning buckets to combinations of pigs and rounds, you can uniquely encode bucket identities. The number of pigs needed grows logarithmically with buckets. This interpretation works well if you view pigs as bits in a positional encoding scheme.

Approach 2: State Expansion Strategy (O(p * r) time, O(p) space)

Instead of binary outcomes, observe that a pig has multiple possible states: it may die in round 1, round 2, ..., round r, or survive all rounds. That gives r + 1 states per pig. With multiple pigs, the total distinguishable outcomes become (r + 1)^p. The algorithm incrementally increases the number of pigs until the total states cover all buckets. This reasoning resembles state expansion used in dynamic programming, where combinations of states encode the final answer.

Approach 3: Mathematical Representation Using States (O(1) time, O(1) space)

The key insight is that pigs form a positional number system where each pig represents a digit with base (r + 1). If a pig dies in round i, that digit equals i. If it survives, the digit equals r. With p pigs you can encode (r + 1)^p unique outcomes, which must be at least the number of buckets. Solve the inequality (r + 1)^p >= buckets and compute p = ceil(log(buckets) / log(r + 1)). This mathematical approach leverages concepts from math and combinatorics, and it produces the cleanest constant-time solution.

Approach 4: Binary Search for Minimum Pigs (O(log buckets) time, O(1) space)

Another practical method is to binary search the number of pigs. For a candidate p, compute how many buckets can be tested using (r + 1)^p. If that value is smaller than the required buckets, increase p; otherwise reduce it. This avoids logarithm formulas and is convenient in languages where precision or overflow may matter.

Recommended for interviews: The mathematical state representation is the expected solution. Interviewers look for the insight that each pig contributes r + 1 distinguishable states, turning the problem into a combinatorial encoding problem. Explaining the state reasoning first and then deriving (r + 1)^p >= buckets demonstrates strong problem-solving ability.

Approach 1: Binary Strategy

Given the problem's constraints and the binary outcomes (either a pig dies or it doesn't), think of the problem in terms of binary representations. A pig can sample several buckets at once, die or survive based on which buckets contain poison. This gives a binary outcome for each test. By using logarithmic calculations with the number of possible outcomes, you can determine the number of states (base 2) that each pig can check within the available time.

Python

import math

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

This solution leverages the mathematical relationship between the problem variables. The number of tests each pig can take during the allocated time is minutesToTest // minutesToDie. Since each pig can be in one of several states (dead/alive), each state helps narrow down the possibilities. Using logarithms, you derive the minimum number of pigs required to cover all buckets.

Complexity

Time Complexity: O(1). The use of logarithmic calculations on constants results in constant time complexity.
Space Complexity: O(1). The storage used does not scale with input size.

Try this approach in the editor

Approach 2: State Expansion Strategy

In this approach, consider how many different states each pig can "check" through its outcome. Since a pig can be either alive or dead at the end of testing, each pig effectively provides binary outcomes, which can be thought of as a base. The total number of scenarios (outcomes) that can be tested is the product of the number of states each pig can obtain.

Python

import math

def poor_pigs(buckets: int, minutesToDie: int, minutesToTest: int) -> int:
    states = minutesToTest // minutesToDie + 1
    pigs = 0
    while (states ** pigs) < buckets:
        pigs += 1
    return pigs

This implementation iteratively increases the number of pigs until the number of scenarios they can test matches or exceeds the number of buckets. Each pig increases the power in which states (base) are multiplied, and hence increases the number of possible outcomes they can cover.

Complexity

Time Complexity: O(log(buckets)). The loop iteratively increases until states raised to pigs is greater or equal to buckets, which is logarithmic relative to the base determined by the states.
Space Complexity: O(1). The memory usage is constant.

Try this approach in the editor

Approach 3: Mathematical Representation Using States

To solve this problem, we need to understand how many states or outcomes a single pig can have. Given the time constraint, a pig can have two states after testing a bucket: it dies, or it survives. If
we allow for tests over a given time duration, a single pig can represent multiple states by modifying the test configuration over time. In essence, with x pigs and y tests, the states can be represented as (y + 1)^(x), where (y + 1) accounts for the initial baseline test and each subsequent test outcome.
Therefore, for 'n' buckets, the equation becomes (minutesToTest / minutesToDie + 1) ^ pigs >= buckets. We solve for pigs using logarithms, over a bounded integer domain.

Python

import math

def poorPigs(buckets, minutesToDie, minutesToTest):
    tests = minutesToTest // minutesToDie
    return math.ceil(math.log(buckets) / math.log(tests + 1))

Java

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int tests = minutesToTest / minutesToDie;
        return (int)Math.ceil(Math.log(buckets) / Math.log(tests + 1));
    }
}

C++

#include <cmath>

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int tests = minutesToTest / minutesToDie;
        return static_cast<int>(ceil(log(buckets) / log(tests + 1)));
    }
};

JavaScript

function poorPigs(buckets, minutesToDie, minutesToTest) {
    const tests = Math.floor(minutesToTest / minutesToDie);
    return Math.ceil(Math.log(buckets) / Math.log(tests + 1));
}

#include <math.h>

int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int tests = minutesToTest / minutesToDie;
    return (int)ceil(log(buckets) / log(tests + 1));
}

using System;

public class Solution {
    public int PoorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int tests = minutesToTest / minutesToDie;
        return (int)Math.Ceiling(Math.Log(buckets) / Math.Log(tests + 1));
    }
}

In Python, the math library provides easy access to logarithmic and rounding operations. The solution proceeds by calculating the number of tests possible and solving the core equation for pigs.

Complexity

Time Complexity: O(1) - Calculation involves basic mathematical operations.
Space Complexity: O(1) - Only constant space is used.

Try this approach in the editor

Approach 4: Binary Search for Minimum Pigs

Another perspective involves using a binary search. This method articulates the problem in terms of balancing the number of pigs against the possible combinations of outcomes they represent per test. Use a binary search over the pig count, harnessing calculations to determine whether given a mid-point pig count, all necessary conditions for success are achievable. This method, while initially more complex, offers a systematic exploration of feasible pig counts.

Python

# Binary search approach in Python
def can_test(pigs, tests, buckets):
    return (tests + 1) ** pigs >= buckets


def poor_pigs(buckets, minutesToDie, minutesToTest):
    tests = minutesToTest // minutesToDie
    low, high = 0, buckets
    while low < high:
        mid = (low + high) // 2
        if can_test(mid, tests, buckets):
            high = mid
        else:
            low = mid + 1
    return low

Java

// Binary search approach in Java
class Solution {
    private boolean canTest(int pigs, int tests, int buckets) {
        return Math.pow(tests + 1, pigs) >= buckets;
    }

    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int tests = minutesToTest / minutesToDie;
        int low = 0, high = buckets;
        while (low < high) {
            int mid = (low + high) / 2;
            if (canTest(mid, tests, buckets)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

C++

// Binary search approach in C++
#include <cmath>

class Solution {
    bool canTest(int pigs, int tests, int buckets) {
        return pow(tests + 1, pigs) >= buckets;
    }
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int tests = minutesToTest / minutesToDie;
        int low = 0, high = buckets;
        while (low < high) {
            int mid = (low + high) / 2;
            if (canTest(mid, tests, buckets)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
};

JavaScript

// Binary search approach in JavaScript
function canTest(pigs, tests, buckets) {
    return Math.pow(tests + 1, pigs) >= buckets;
}

function poorPigs(buckets, minutesToDie, minutesToTest) {
    const tests = Math.floor(minutesToTest / minutesToDie);
    let low = 0, high = buckets;
    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (canTest(mid, tests, buckets)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Binary search approach in C
#include <math.h>

int canTest(int pigs, int tests, int buckets) {
    return pow(tests + 1, pigs) >= buckets;
}

int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int tests = minutesToTest / minutesToDie;
    int low = 0, high = buckets;
    while (low < high) {
        int mid = (low + high) / 2;
        if (canTest(mid, tests, buckets)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Binary search approach in C#
using System;

public class Solution {
    private bool CanTest(int pigs, int tests, int buckets) {
        return Math.Pow(tests + 1, pigs) >= buckets;
    }

    public int PoorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int tests = minutesToTest / minutesToDie;
        int low = 0, high = buckets;
        while (low < high) {
            int mid = (low + high) / 2;
            if (CanTest(mid, tests, buckets)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

This Python solution parallels others in logic, emphasizing a streamlined binary search over possible pig values. It checks each midpoint and narrows the bounds efficiently.

Complexity

Time Complexity: O(log n) - Searches possible pig levels via binary log pattern.
Space Complexity: O(1) - Consumes fixed memory space.

Try this approach in the editor

Approach 5: Default Approach

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

Try this approach in the editor

Complexity comparison

Approach	Complexity
Binary Strategy	Time Complexity: O(1). The use of logarithmic calculations on constants results in constant time complexity. Space Complexity: O(1). The storage used does not scale with input size.
State Expansion Strategy	Time Complexity: O(log(buckets)). The loop iteratively increases until states raised to pigs is greater or equal to buckets, which is logarithmic relative to the base determined by the states. Space Complexity: O(1). The memory usage is constant.
Mathematical Representation Using States	Time Complexity: O(1) - Calculation involves basic mathematical operations. Space Complexity: O(1) - Only constant space is used.
Binary Search for Minimum Pigs	Time Complexity: O(log n) - Searches possible pig levels via binary log pattern. Space Complexity: O(1) - Consumes fixed memory space.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Binary Strategy	O(log buckets)	O(1)	When reasoning about pigs as binary indicators across rounds
State Expansion Strategy	O(p * r)	O(p)	When incrementally exploring how many outcomes pigs can encode
Mathematical Representation Using States	O(1)	O(1)	Best approach for interviews and production solutions
Binary Search for Minimum Pigs	O(log buckets)	O(1)	When avoiding logarithmic formulas or handling large numbers safely

Frequently asked questions

Is Poor Pigs easy or hard?

Poor Pigs is labeled Hard on LeetCode because the solution requires a non-obvious combinatorial insight. Once you recognize that pigs represent digits in a base-(r + 1) numbering system, the implementation becomes a short constant-time formula.

How to solve Poor Pigs in O(1)?

Compute the number of testing rounds r = minutesToTest / minutesToDie. Each pig has r + 1 possible outcomes: dying in any round or surviving. Using p pigs produces (r + 1)^p distinguishable outcomes. Solve p = ceil(log(buckets) / log(r + 1)) to get the minimum pigs.

Poor Pigs Python or Java solution

Most implementations compute r = minutesToTest / minutesToDie and return ceil(log(buckets) / log(r + 1)). This logic works identically in Python, Java, C++, C#, and JavaScript because it only relies on logarithmic math functions.

What is the best approach for Poor Pigs?

The optimal approach uses mathematical state encoding. Each pig can end up in r + 1 states where r = minutesToTest / minutesToDie. With p pigs you can distinguish (r + 1)^p buckets. Solve the inequality (r + 1)^p >= buckets to compute the minimum pigs in O(1) time.

What data structure is used in Poor Pigs?

The optimal solution does not rely on traditional data structures. Instead it uses mathematical reasoning and combinatorics to encode bucket identities using pig states across multiple rounds.

What is the time complexity of Poor Pigs?

The optimal mathematical solution runs in O(1) time and O(1) space because it directly computes p = ceil(log(buckets) / log(r + 1)). Alternative strategies such as binary search over pigs take O(log buckets) time.

Is Poor Pigs asked at Google, Amazon, or Meta?

Poor Pigs is a classic mathematical puzzle frequently discussed in interviews at large tech companies including Google, Amazon, and Meta. It tests logical reasoning, combinatorics, and the ability to convert a puzzle into a mathematical model.

Poor Pigs solution and explanation

The problem

Approach overview

Approach 1: Binary Strategy

Approach 2: State Expansion Strategy

Approach 3: Mathematical Representation Using States

Approach 4: Binary Search for Minimum Pigs

Approach 5: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Poor Pigs solution and explanation

The problem

Approach overview

Approach 1: Binary Strategy

Approach 2: State Expansion Strategy

Approach 3: Mathematical Representation Using States

Approach 4: Binary Search for Minimum Pigs

Approach 5: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems