LeetCode Entry
458. Poor Pigs
Minimum pigs to find a poison in buckets in k rounds
458. Poor Pigs hard blog post substack
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/385
Problem TLDR
Minimum pigs to find a poison in buckets in k rounds
Intuition
The first idea is, with the number of pigs increasing, the possibility to successfully test in the given time grows from impossible to possible. This gives us the idea to use a Binary Search.
However, now we must solve another problem: given the pigs and rounds, how many buckets we can test?
One simple insight is: let’s assign unique pigs pattern to each of the bucket.
We can brute-force this problem and use memorization. Consider each pig, it can avoid participation, and can participate in all the rounds:
val dp = mutableMapOf<Int, Int>()
fun numPatterns(pigs: Int): Int {
fun dfs(curr: Int): Int = if (curr == 0) 1 else dp.getOrPut(curr) {
val take = dfs(curr - 1)
if (take >= buckets) take else take + take * minutesToTest / minutesToDie
}
return dfs(pigs)
}
This number grows quickly, so we trim it by the buckets number maximum.
Another way to solve this, is to observe those unique patterns.
If we have just one round, 3 pigs, there are total 8 patterns:
// pigs = 3 rounds = 1
// 123
// 0 000 no pig drinks
// 1 001 pig #3 drinks
// 2 010 pig #2 drinks
// 3 011 pigs #2 and #3 drinks
// 4 100 pig #1 drinks
// 5 101 pigs #1 and #3 drinks
// 6 110 pigs #1 and #2 drinks
// 7 111 all pig drinks
or,
//
// 0 1 2 3 4 5 6 7
// 1 1 1 1 <-- pig #1
// 2 2 2 2 <-- pig #2
// 3 3 3 3 <-- pig #3
Now, if one bucket is a poison, we immediately know which one of those 8 buckets by its unique pattern.
Ok, so 3 pigs for 1 round enables to test 8 or 2^3 buckets. It is evident, that for 1 round the number of possible buckets is 2^pigs
How this changes with the growth of rounds? Let’s observe another example, 3 pigs, 2 rounds:
//
// 3 pigs, 2 rounds:
// 123
// 0 000
// 1 001
// 2 002
// 3 010
// 4 011
// 5 012
// 6 020
// 7 021
// 8 022
// 9 100
//10 101
//11 102
//12 110
//13 111
//14 112
//15 120
//16 121
//17 122
//18 200
//19 201
//20 202
//21 210
//22 211
//23 212
//24 220
//25 221
//26 222
or,
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
// - round 1 -
// 1 1 1 1 1 1 1 1 1
// 2 2 2 2 2 2 2 2 2
// 3 3 3 3 3 3 3 3 3
// - round 2 -
// 1 1 1 1 1 1 1 1 1
// 2 2 2 2 2 2 2 2 2
// 3 3 3 3 3 3 3 3 3
Each pigs pattern consists of the 3 pigs, and each pig defined as round 1 or round 2.
This results in 27 unique patterns, or buckets being able to test, or 3^3. Let’s extrapolate this formula: buckets = (1 + rounds) ^ pigs
Approach
For better Binary Search, use:
- inclusive
loandhi - check the last condition
lo == hi - always move
loorhi - always compute the result independently
min = min(min, mid)
Complexity
-
Time complexity: \(O(log^2(buckets))\), one
logfor the Binary Search, another is forcanTestfunction -
Space complexity: \(O(1)\)
Code
DFS + memo
fun poorPigs(buckets: Int, minutesToDie: Int, minutesToTest: Int): Int {
val dp = mutableMapOf<Int, Int>()
fun numPatterns(pigs: Int): Int {
fun dfs(curr: Int): Int = if (curr == 0) 1 else dp.getOrPut(curr) {
val take = dfs(curr - 1)
if (take >= buckets) take else take + take * minutesToTest / minutesToDie
}
return dfs(pigs)
}
var lo = 0
var hi = buckets
var min = hi
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
if (numPatterns(mid) >= buckets) {
min = min(min, mid)
hi = mid - 1
} else lo = mid + 1
}
return min
}
The more clever version:
fun poorPigs(buckets: Int, minutesToDie: Int, minutesToTest: Int): Int {
fun canTest(pigs: Int): Boolean {
var p = 0
var bs = 1
while (p++ < pigs) {
bs *= 1 + minutesToTest / minutesToDie
if (bs >= buckets) return true
}
return bs >= buckets
}
var lo = 0
var hi = buckets
var min = hi
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
if (canTest(mid)) {
min = min(min, mid)
hi = mid - 1
} else lo = mid + 1
}
return min
}