LC-0458 Hard LeetCode

458. Poor Pigs

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 59% Topics: Math, Dynamic Programming, Combinatorics

Reading material

Math & Geometry 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

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

import math


class Solution(object):
    def poorPigs(self, buckets, minutesToDie, minutesToTest):
        """
        :type buckets: int
        :type minutesToDie: int
        :type minutesToTest: int
        :rtype: int
        """
        return int(math.ceil(math.log(buckets) / math.log(minutesToTest / minutesToDie + 1)))

Solution from kamyu104/LeetCode-Solutions · MIT