[C++] Concise Solution, 100% Time, 60% Space
This was really a thought provoking and worth the effort, although maybe it was more of a medium than a hard.\n\nTo figure out how to solve it we can go multipl
This was really a thought provoking and worth the effort, although maybe it was more of a medium than a hard.\n\nTo figure out how to solve it we can go multiple paths, but let\'s go with the one I find myself to be more intuitive - assuming we only have one round of tests.\n\nNow, let\'s say we want to test `16` buckets and with one sole pig we might take up to `16` attempts (testing each single bucket one by one), so clearly not in range of our thought experiment with only one trial.\n\nWith 2 pigs, we might try to play a bit smart:\n* the first pig would drink from the first 8 buckets;\n* the second one would drink from the `5 - 12` range (counting from `1`) of buckets.\n\n```cpp\n// 1 = that pig drunk from this bucket, 0 = that pig skipped it\np1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0\np2 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0\n```\n\nThis way, we might have the boil down the possible buckets to just `4`, via a logical `AND`:\n* easiest case - if both pigs die, it has to be some bucket in the `5 - 8` range;\n* conversely, if both survive, the poison that we know is in just one bucket, has to be in the `13 - 16` range;\n* alternative pigs surviving will tell us that it is either in the `1 - 4` (first pig dying, second pig surviving) or `9 -12` (the other way around) range.\n\nFast forward and you can see how parsing all our 16 buckets in one go might require `4` pigs, to have a unique combination for each bucket - it is just binary composition, in a way.\n\nSame if we had any number of buckets `> 8`, but still `<= 16`.\n\nMore in general, we can conclude that the number of required pigs to check `buckets` possibilities in one single attempt is equal to `log2(buckets)`, rounded up.\n\nWhat if we have multiple chances, then?\n\nWell, in that case we can just split the problem into `buckets / numberOfAttempts` copies of the problem we just discussed (solving with just one trial).\n\nNow, we know that the number of possible attempts it is equal to `totalTimeToTest / minutesToDie + 1` (`+ 1` since it we can wait after the time is over to check what happens to the pigs after their last drink), so doing the last bit of math, we can end up with the final formula.\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int poorPigs(int buckets, int poisonTime, int totalTime) {\n        return ceil(log(buckets) / log(totalTime / poisonTime + 1));\n    }\n};\n```
['Math', 'C', 'C++']