Poor Pigs

hard math combinatorics

Problem

Given some buckets where exactly one contains poison, find the minimum number of pigs needed to identify the poisoned bucket within minutesToTest, given each test cycle takes minutesToDie minutes.

Inputbuckets = 1000, minutesToDie = 15, minutesToTest = 60

Output5

t = 60/15 + 1 = 5; 5⁵ = 3125 ≥ 1000.

buckets

die

test

import math
def poor_pigs(buckets, dieM, testM):
    t = testM // dieM + 1
    return math.ceil(math.log(buckets) / math.log(t))

function poorPigs(buckets, dieM, testM) {
  const t = Math.floor(testM / dieM) + 1;
  return Math.ceil(Math.log(buckets) / Math.log(t));
}

class Solution {
    public int poorPigs(int buckets, int dieM, int testM) {
        int t = testM / dieM + 1;
        return (int) Math.ceil(Math.log(buckets) / Math.log(t));
    }
}

int poorPigs(int buckets, int dieM, int testM) {
    int t = testM / dieM + 1;
    return (int) ceil(log(buckets) / log(t));
}

Explanation

This is really an information-counting puzzle. Each pig can be fed at different test rounds, and the round in which it dies (or that it survives) encodes a number — so a few pigs can together point to one bucket out of many.

First figure out how many distinguishable outcomes one pig has. With minutesToTest / minutesToDie feeding rounds available, a pig can die after round 1, round 2, …, or survive all of them. That gives t = minutesToTest // minutesToDie + 1 possible outcomes per pig.

With k pigs, each independently having t outcomes, you can label t^k different buckets. So you need the smallest k with t^k >= buckets, which is exactly k = ceil(log_t(buckets)), computed as ceil(log(buckets) / log(t)).

Example: buckets = 1000, die = 15, test = 60. Then t = 60/15 + 1 = 5, and 5^5 = 3125 >= 1000 while 5^4 = 625 is too small, so the answer is 5 pigs.

It is just a couple of arithmetic and log operations, so it runs in constant time and space.

Time: O(1) Space: O(1)