c++ log2 solution explained
Introduction\n Describe your first thoughts on how to solve this problem. \nThis is an attempt to provide a better explanation for the optimal solution, since I
# Introduction\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is an attempt to provide a better explanation for the optimal solution, since I haven\'t seen any good explanations yet.\n\nI also hope this post provides you with some ideas how to approach similar problems. \n\n\n# Explanation\n<!-- Describe your approach to solving the problem. -->\nTo begin with, notice that we have `m = timeTest/ timeDetect` trials or runs, before we need to know which bucket is poisoned. And if we have `n` pigs, then we can test `(m+1)^n` buckets for poison. The below is a detailed explanation and a proof. \n\n## Base case\nConsider a base case where `m = 1` and suppose we have `n` pigs. Then we can test `2^n` buckets. To see this, consider how many possible outcomes there are at the end of the run. After one run, each pig might be dead or alive and there are `n` pigs, so there are `2^n` different outcomes. \n\nConsider these possible outcomes in binary representation, suppose we have an outcome as follows\n\n```\noutcome = 00011110000111\n```\n\nwhere `i-th` digit corresponds to whether `i-th` pig survived or not. \nWe need to show that a mapping exists between binary representations and ways to assign the buckets. And we don\'t need to find them, just knowing that such a mapping exists is sufficient! \n\nActually, it is straighforward. Label buckets from `0` to `2^n - 1`, convert the bucket label number to binary representation, and assign this bucket to pig `i` if and only if the `i-th` binary digit is 1. \n\nFor instance, bucket `3` has binary representation `0011`, hence, bucket three is assigned to pigs `0` and `1`. \n\nIn summary, with one run and `n` pigs we can test `2^n` different buckets.\n\n\n## General case\nNow consider a general case where `m > 1` and suppose we have `n` pigs. What happens now? \n\nWell, let us try calculating the number of different outcomes. We have `m` trials or runs. Every pig might die at any of the trials or it might survive till the end. So every pig has `m+1` possible outcomes. And there are `n` pigs. \n\nHence, there are at most `(m+1)^n` different outcomes. \n\nHowever, we can still find a mapping between all these different outcomes and ways to assign buckets to pigs. \n\nInstead of binary representation, consider `(m+1)`-ry representation. \nFor simplicity let us take `m = 2`, then outcomes have the following form\n\n```\noutcome = 0212100120201\n```\n\nWhat does it mean? Digit at `i-th` place indicates on which trial or run the corresponding pig died. `2` means that the pig survived till the end. \n\nHow can we map it to bucket assignments? Well, as before, label every bucket from `0` to `(m+1)^n - 1` and convert this number to `(m+1)`-ry representation. Now a digit `k` at `i-th` place means that we give this bucket to pig `i-th` on trial or run `k` (`k = m` means we don\'t give this bucket to pig `i-th`). Hence, we have our mapping! \n\nWe run the test completely, and knowing which pig died when (or survived) will give us a binary representation, which we can then convert to the bucket number! \n\nThis completes the proof. \n \n\n# Wrap up\n\nThe problem boils down to finding `n` such that `(m+1)^n > buckets`. Taking the logs, changing the logs base and rearranging gives the required form as in the code below. \n\n\n# Complexity\n- Time complexity: O(1)\n\n- Space complexity: O(1)\n\n# Code\n```\nclass Solution \n{\npublic: int poorPigs(int buckets, int timeDetect, int timeTest)\n{\n    return ceil(log2(buckets)/log2(int(timeTest/timeDetect)+1));\n}\n};\n```
['Math', 'C++']