Poor Pigs - Video Solutions

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.