Leetcode: 458. Poor Pigs

Problem Statement

• Mistake: Failed to consider different strategies to solve the problem. I was stuck on trying to compute the minimum number of tries given a number of pigs and buckets.
• Mistake: Failed to consider different strategies to solve the problem. I saw that two pigs with one could cover at most \(2^x\) buckets, but failed to see how to extend this the second, third and so on tries.
• Can we simplify the problem while keeping it the same? Given that \(x\) pigs and one try, we know that they can find the solution for at most \(2^x\) buckets. This is so because each bucket has an unique id in the base 2. To represent the next try, we have to increase the base. So, all buckets will have an unique id which means that an unique combination of pigs die maps to only one bucket. Time complexity is \(O(\log_b n)\) where \(n\) is the number of buckets and \(b\) is the number of tries. Space complexity is \(O(1)\).

from math import comb


class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        digits = ceil(minutesToTest / minutesToDie + 1)
        cur = 1
        ans = 0
        while cur < buckets:
            cur *= digits
            ans += 1
        return ans


assert Solution().poorPigs(1000, 15, 60) == 5
assert Solution().poorPigs(4, 15, 15) == 2
assert Solution().poorPigs(4, 15, 30) == 2