Math | Different approach: Writing buckets in other base
This solution yields the same popular one-liner solution, but the inspiration behind it is different and does not use the provided hints.\n\n### One-liner\n\nWe
This solution yields the same popular one-liner solution, but the inspiration behind it is different and does not use the provided hints.\n\n### One-liner\n\nWe just need to find the ***number of digits*** of `buckets` in ***base*** `minutesToTest // minutesToHeaven + 1`<sup>**</sup>. This is given by\n```python\n        return ceil(log(buckets, minutesToTest // minutesToHeaven + 1))\n```\n<sup>** Except in the case where   buckets   is a power of   (minutesToTest // minutesToHeaven + 1) in which case the answer is one less than the number of digits.</sup>\n\n<hr>\n\n### The idea explained with an example\n\nIf we think of a pig "going to heaven" as a ***successful test*** \uD83D\uDE2D, we can think in `0`s and `1`s. Consider a chain of binary numbers with `pigs` digits and where we have one less pig available each time.\n\nFor example\n```text\n1 0 0 0 0  ->  1 0 0 0 0  -> pig 1 goes to heaven\n \xA00 1 0 0  ->  x 0 1 0 0  -> pig 3 goes to heaven\n \xA0 \xA00 1 0  ->  x 0 x 1 0  -> pig 4 goes to heaven\n      1 0  ->  x 1 x x 0  -> pig 2 goes to heaven\n```\nwould mean the poisonous bucket was tested by pigs 1, 3, 4, and 2. Of course we would like to be sure that we have the poisonous bucket at the end, so we would assume the last test was definitive. We have a time limit, so we can do at most `timeToTest // minutesToTest` tests.\n\nUsing the chains of binary digits from the second to the last test <ins>we can build a number</ins> that is somewhere between `0` and `timeToTest // minutesToTest`, so we can essentially think of `buckets` as a number in base `timeToTest // minutesToTest + 1`. Remember that a number in base `a` is a sequence of "digits" that range from `0` to `a - 1`. This means we need as many pigs as the number of digits of `buckets` in base `timeToTest // minutesToHeaven + 1`.\n\n>The number of digits of a number `a` in base `b` is given by `floor(log(a, b)) + 1`, so we would need\n>```python\n>\t\tfloor(log(buckets, floor(minutesToTest / minutesToHeaven) + 1)) + 1\n>```\n>pigs.\n\n**Note:** This approach goes over by `1` when `buckets` is a power of `timeToTest // minutesToHeaven + 1`. This is because in such case we can set aside one bucket and work with `buckets - 1` buckets (if `buckets = 100...0` then `buckets - 1 = 11...1` thus having one less digit). If we don\'t find the culprit among those `buckets - 1` buckets, then we know the one we set aside ***is*** the poisonous one (saving all pigs in the process!! \uD83E\uDD73), thus needing one less pig than what the formula above gives. The stuff inside the `floor` will be an integer in this case (and only in this case) so the formula above agrees with\n```python\n\t\tceil(log(buckets, floor(minutesToTest / minutesToHeaven) + 1))\n```\nand fixes this issue.\n\n<hr>\n\n* Shoutout to [@sir_rishi](https://leetcode.com/sir_rishi/) for helping figure out why the approach failed for powers of `timeToTest // minutesToHeaven + 1`.\n\n
['Math']