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.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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:
- 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).
- Wait
minutesToDieminutes. A pig that drank the poison dies at the end of the wait; the others survive. No other feeding can happen during the wait. - 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 <= 10001 <= minutesToDie <= minutesToTest <= 100
Hints for Poor Pigs
Hint 1
With
T = floor(minutesToTest / minutesToDie)rounds, a single pig's fate hasT + 1outcomes: it dies after round 1, after round 2, …, or survives.Hint 2
Pigs are independent, so
ppigs can produce(T + 1)^pdistinguishable outcomes.Hint 3
Find the smallest
pwith(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
- Compute
states = minutesToTest / minutesToDie + 1(integer division). - Start with
pigs = 0andreach = 1(one bucket needs no test). - While
reach < buckets, multiplyreachbystatesand add a pig. - 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, notT— 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 pigsJava
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