Three steps thinking process for poor pigs
---\nStep I -- Consider the reverse of the problem\n\nSuppose the total number of permissible tests are fixed, instead of thinking about the minimum number of p
---\n**`Step I -- Consider the reverse of the problem`**\n\nSuppose the total number of permissible tests are fixed, instead of thinking about the **minimum number of pigs** needed to find the poisonous bucket from the given number of buckets, let's consider the reverse: what is the **maximum number of buckets** from which we are able to find the poisonous one with the given number of pigs?\n\nTo make our problem more clear, let's define `T(n, k)`, which will be the **maximum number of buckets** from which we can determine the poisonous one with `n` pigs and `k` tests. Our mission is to find the general expression of `T(n, k)` in terms of `n` and `k` (we will assume `k > 0`, otherwise there can be only `1` bucket, the one with poison which can be identified without any testing).\n\n---\n**`Step II -- Consider cases with only 1 pig`**\n\nLet's start with simple cases when there is only `1` pig at our disposal, i.e., `n = 1`. \n\nFirst given a bucket, how do we determine if it is poisonous or not? Well, we have got no better way other than feed the pig with its "water"(**can be poisonous!**) and check if the pig dies after some time. If it does, bingo we've found the right one. Or if the pig is lucky to be alive, we are still able to eliminate one bucket. \n\nCan we feed the pig with "water" from **two or more** buckets simultaneously? No. Because if the pig dies after drinking "water" from those buckets, we won't be able to nail down the exact one which is poisonous as there are no more live pigs, even if we are permitted to do more tests.\n\nSo with one pig, for each attempt, we can either find the poisonous bucket or eliminate an "innocent" one, depending on the status of the pig (dead or alive).\n\nIf only one test is allowed, i.e., `k = 1`, from the analyses above, we can either determine one bucket is poisonous or eliminate it. If the total number of bucket is `1`, we surely can find the poisonous bucket (which is just the one given). If the total number of bucket is '2', since testing results of one bucket will automatically reveal information about the other, we can still determine which of the two is poisonous. But if we have more than `2` buckets, we won't be able to make sure which one of the rest contains poison if the pig survives the test with one bucket at our choice, since we've run out of tests. Therefore, in this case, there can be at most two buckets from which we may be able to find the poisonous one with `1` pig and `1` test, or in a symbolic way, `T(1, 1) = 2`.\n\nHow about there are `k` tests permissible? Apparently we can check at least `k` buckets with `k` tests, so `T(1, k) >= k`. Can we do better? The key is to consider the extreme case when the pig survives all `k` tests (what a lucky pig, btw). How many more buckets can be left unchecked if we were able to figure out the poisonous one? The answer is `1` since we cannot do any more test so there has to be a way for us to point at a bucket and say it is poisonous with 100% sure. Therefore, we have `T(1, k) = k + 1`.\n\n---\n**`Step III -- Consider general cases with n pigs`**\n\nFrom part `II`, we know there are at most `k + 1` buckets from which a poisonous one can be determined with `1` pig and `k` tests, or `T(1, k) = k + 1`. Now we have n pigs, and testing of each pig is **independent** from each other (feeding "water" to a pig is independent from feeding others, provided each bucket has enough "water"), we are free to combine the `k + 1` results of each pig and end up with `(k + 1)^n` total combinations.\n\nSo without digging deeper, we've found the general expression: `T(n, k) = (k + 1)^n`. And you can happily proceed to figure out the answer for the original problem. But in case you are wondering how exactly we will carry out the tests and do "combination" of the results, here is one possible interpretation.\n\nSuppose we have `N` total buckets from which the poisonous one is to be found. `n` is the minimum number of pigs such that `T(n, k) >= N`, with `T(n, k) = (k + 1)^n` and `k >= 1`. We can label all the buckets from `0` up to `N - 1` and express each of them as a number in the base-`(k + 1)` numeral system. Each pig will represent one digit for a number in the same numeral system (marked as pig `0` to `n - 1`, from least significant digit to most significant one). Since our final goal is equivalent to determining all the `n` digit values of the number of the poisonous bucket, we can do so by testing each value one by one since there are at most `k + 1` possible values for each digit, which can be done within `k` tests. Here is the detailed way to accomplish that: In the `1st` test, for each pig, feed it with "water" from all buckets whose number has a digit value of `1` at the corresponding digit. In the `2nd` test, for all **live** pigs, feed it with "water" from all buckets whose number has a digit value of `2` at the corresponding digit. And so on until either all pigs are dead or we've run out of tests. In either case the number of the poisonous bucket is guaranteed to be found.\n\nIf you are interested in examples for this interpretation, [ifyouseewendy](https://discuss.leetcode.com/topic/67482/solution-with-detailed-explanation) has done a great job here. \n\nAnother interpretation is to associate each pig with one dimension of a multi-dimensional array, as explained by [StefanPochmann](https://discuss.leetcode.com/topic/67666/another-explanation-and-solution). We first arrange all buckets into this multi-dimensional array. Then in each test, we feed each **live** pig with "water" from "one unit" of buckets belonging to the corresponding dimension (for example, in the `1st` test, feed pig `1` with all the `1st` rows; feed pig `2` with all the `1st` columns; feed pig `3` with all the `1st` pages...; in the `2nd` test, if pig `1` is still alive, feed it with all the `2nd` rows; if pig `2` is still alive, feed it with all the `2nd` columns; if pig `3` is still alive, feed it with all the `2nd` pages....). At the end of the test, all the indices of the poisonous bucket will be determined so we can index into the multi-dimensional array to find it.\n\nThe final code is rather simple once we've figured out the expression for `T(n, k)`. Some minor issues are dealing with corner cases such as only `1` bucket or it takes more time for the pig to die than it is allowed to wait. Also pay attention to computing logarithm for integers. Here is the Java program.\n\n```\npublic int poorPigs(int buckets, int minutesToDie, int minutesToTest) {\n    if (buckets < 2) return 0;\n    if (minutesToDie > minutesToTest) return Integer.MAX_VALUE;\n    \n    int k = minutesToTest / minutesToDie;\n    return (int)Math.ceil((Math.log(buckets) / Math.log(k + 1)));\n}\n```
[]