We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Poor Pigs

Number: 458

Difficulty: Hard

Paid? No

Companies: Adobe, Amazon

Problem Description

Given a number of buckets with exactly one poisonous bucket, determine the minimum number of pigs required to identify the poisonous bucket within a limited amount of testing time. A pig dies if it drinks from the poisonous bucket during a test round that lasts minutesToDie, and tests can be repeated within the total minutesToTest available. The challenge is to design a testing strategy that minimizes the number of pigs required.

Key Insights

  • A pig can have (rounds + 1) distinct outcomes: it might die in one of the rounds or survive all rounds.
  • The total number of rounds is rounds = minutesToTest / minutesToDie.
  • With p pigs and (rounds + 1) possible outcomes per pig, the total number of distinct outcomes is (rounds + 1)^p.
  • The minimum number of pigs p must satisfy (rounds + 1)^p ≥ buckets.

Space and Time Complexity

Time Complexity: O(1) – The computation involves logarithmic and division operations, independent of the input size. Space Complexity: O(1) – Only a few variables are used, regardless of the input size.

Solution

The solution leverages the combinatorial insight that each pig can represent multiple outcomes (i.e., which round it dies in, or if it survives all rounds). First, compute the number of rounds available by dividing minutesToTest by minutesToDie. Then, find the smallest integer p such that (rounds + 1)^p is at least equal to the number of buckets. This is done by solving p ≥ log(buckets) / log(rounds + 1) and taking the ceiling of that value. This mathematical approach minimizes the number of pigs needed by maximizing the diagnostic power of each pig through a multi-round testing strategy.

Code Solutions

# Import math to use the ceiling and logarithm functions.
import math

def poor_pigs(buckets, minutesToDie, minutesToTest):
    # Calculate the number of rounds available for testing.
    rounds = minutesToTest // minutesToDie
    # The base for each pig's outcome: survives or dies in a specific round.
    # Find the minimum number of pigs needed such that (rounds + 1)^p >= buckets.
    pigs = math.ceil(math.log(buckets, rounds + 1))
    return pigs

# Example usage:
print(poor_pigs(4, 15, 15))  # Expected output: 2
print(poor_pigs(4, 15, 30))  # Expected output: 2
← Back to All Questions