Poor Pigs

This page explains Java solution to problem Poor Pigs using Math.

Problem Statement

There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?

Answer this question, and write an algorithm for the general case.

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the poisonous bucket within p minutes? There is exactly one bucket with poison.

Input: buckets = 1000, minutesToDie = 15, minutesToTest = 60
Output: 5

Solution

package com.vc.hard;

class PoorPigs {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        /**
             If we have 1 attempt we have Two states
             -Pig is Alive
             -Pig is Dead

             If we have 2 attempts we have Three states
             -Pig is Alive
             -Pig is Dead After 1st attempt
             -Pig is Dead After 2nd attempt

             And so on...

             Now think of states as Base and Bucket as Number to represent, how many digits are needed
        */
        int attempts = minutesToTest / minutesToDie;
        int states = attempts + 1;
        return (int)Math.ceil(Math.log(buckets) / Math.log(states));
    }
}

Time Complexity

O(1)

Space Complexity

O(1)