Poor Pigs

Hard
1277.

Poor Pigs

Poor Pigs is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon and Google interviews.

Exactly one of buckets buckets of liquid is poisoned, and you want to find out which one using pigs, within minutesToTest minutes.

Testing works in rounds:

  1. Choose some live pigs and let each of them drink from any set of buckets (simultaneously, taking no time; a bucket may be shared by many pigs and a pig may drink from many buckets).
  2. Wait minutesToDie minutes. A pig that drank the poison dies at the end of the wait; the others survive. No other feeding can happen during the wait.
  3. Repeat with the surviving pigs while time remains.

Return the minimum number of pigs that guarantees identifying the poisoned bucket within the time limit.

Example 1

Input
buckets = 4, minutesToDie = 15, minutesToTest = 15
Output
2
Explanation
One round. Pig A drinks buckets 1 and 2, pig B drinks buckets 2 and 3. Their four possible fates (A dies, B dies, both, neither) name the bucket.

Example 2

Input
buckets = 4, minutesToDie = 15, minutesToTest = 30
Output
2

Example 3

Input
buckets = 1000, minutesToDie = 15, minutesToTest = 60
Output
5

Constraints

  • 1 <= buckets <= 1000
  • 1 <= minutesToDie <= minutesToTest <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} buckets
 * @param {number} minutesToDie
 * @param {number} minutesToTest
 * @return {number}
 */
var poorPigs = function(buckets, minutesToDie, minutesToTest) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Poor Pigs — Solution in Python, Java & C++

Poor Pigs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Poor Pigs is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon and Google interviews.

Problem statement

Exactly one of buckets buckets of liquid is poisoned, and you want to find out which one using pigs, within minutesToTest minutes.

Testing works in rounds:

  1. Choose some live pigs and let each of them drink from any set of buckets (simultaneously, taking no time; a bucket may be shared by many pigs and a pig may drink from many buckets).
  2. Wait minutesToDie minutes. A pig that drank the poison dies at the end of the wait; the others survive. No other feeding can happen during the wait.
  3. Repeat with the surviving pigs while time remains.

Return the minimum number of pigs that guarantees identifying the poisoned bucket within the time limit.

Example 1

Input: buckets = 4, minutesToDie = 15, minutesToTest = 15
Output: 2
Explanation: One round. Pig A drinks buckets 1 and 2, pig B drinks buckets 2 and 3. Their four possible fates (A dies, B dies, both, neither) name the bucket.

Example 2

Input: buckets = 4, minutesToDie = 15, minutesToTest = 30
Output: 2

Example 3

Input: buckets = 1000, minutesToDie = 15, minutesToTest = 60
Output: 5

Constraints

  • 1 <= buckets <= 1000
  • 1 <= minutesToDie <= minutesToTest <= 100

Hints for Poor Pigs

  1. Hint 1

    With T = floor(minutesToTest / minutesToDie) rounds, a single pig's fate has T + 1 outcomes: it dies after round 1, after round 2, …, or survives.

  2. Hint 2

    Pigs are independent, so p pigs can produce (T + 1)^p distinguishable outcomes.

  3. Hint 3

    Find the smallest p with (T + 1)^p >= buckets — and show that many outcomes can always be realised.

How to solve Poor Pigs

A pig is a digit in base T + 1, where T is the number of rounds: the round it dies in (or survival) is its digit, so p pigs can tell apart (T + 1)^p buckets.

Approach

  1. Compute states = minutesToTest / minutesToDie + 1 (integer division).
  2. Start with pigs = 0 and reach = 1 (one bucket needs no test).
  3. While reach < buckets, multiply reach by states and add a pig.
  4. Return pigs.

Why it works

Upper bound: number the buckets 0 … buckets−1 in base T + 1 with p digits. In round r, pig j drinks from every bucket whose j-th digit is r. If the poison's j-th digit is d, pig j dies in round d (or survives when d = T), so the fates spell out the poisoned bucket's number. Lower bound: each pig's whole history is one of T + 1 outcomes, so p pigs produce at most (T + 1)^p different observations, and two buckets with the same observation cannot be told apart. Hence the smallest p with (T + 1)^p >= buckets is exact.

Complexity

  • Time — O(log buckets)
  • Space — O(1)

Pitfalls

  • One bucket needs zero pigs.
  • The base is T + 1, not T — survival is an outcome too.
  • Floating-point logarithms can round log(125)/log(5) to 3.0000000004 and add a pig; multiply integers instead.

Reference solution

Python

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

Java

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

C++

int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int states = minutesToTest / minutesToDie + 1;
    int pigs = 0;
    long long reach = 1;
    while (reach < buckets) {
        reach *= states;
        pigs++;
    }
    return pigs;
}

JavaScript

var poorPigs = function(buckets, minutesToDie, minutesToTest) {
    var states = Math.floor(minutesToTest / minutesToDie) + 1;
    var pigs = 0, reach = 1;
    while (reach < buckets) {
        reach *= states;
        pigs++;
    }
    return pigs;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming