How Many Pigs Do You Need to Find a Poisoned Bucket? Solution Explained

A recent incident where a contractor uploaded a company’s marketing system source code and a year’s worth of revenue data to GitHub highlighted the serious consequences of lax information security.

The article uses this reminder to transition into a technical discussion of LeetCode’s “Poor Pigs” problem, which asks for the smallest number of pigs required to guarantee identification of a poisoned bucket.

Problem Statement

Given buckets, minutesToDie, and minutesToTest, determine the minimum number of pigs needed so that, after feeding experiments, the poisoned bucket can always be identified.

Mathematical Model

Each pig can be tested rounds = minutesToTest / minutesToDie times, yielding states = rounds + 1 possible outcomes (die in round 1, 2, … or survive). With p pigs we can distinguish up to (states)^p buckets. The goal is the smallest p satisfying (states)^p >= buckets.

(rounds + 1)^p >= buckets

Example Calculation

For buckets = 1000, minutesToDie = 15, minutesToTest = 60 we have rounds = 4 and states = 5. Powers of 5 show that 5 pigs can cover 3125 buckets (5⁵ ≥ 1000), so the answer is 5.

Reference Implementation (Java)

public class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int rounds = minutesToTest / minutesToDie;
        int states = rounds + 1;
        int pigs = 0;
        long capacity = 1;
        while (capacity < buckets) {
            pigs++;
            capacity *= states;
        }
        return pigs;
    }
}

Explanation: rounds is the number of feeding opportunities, states is the number of distinct outcomes per pig, and capacity tracks how many buckets the current number of pigs can theoretically distinguish. The loop increments pigs until capacity meets or exceeds buckets.