458. Poor Pigs

二刷 08/2022

Version #1 Math

什么玩意

看答案才能做得出来

Math.ceil return的是double

Time O(1)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Poor Pigs.

Memory Usage: 38.9 MB, less than 95.20% of Java online submissions for Poor Pigs.

class Solution {

    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {

        // states^x >= buckets

        int states = minutesToTest / minutesToDie + 1;

        // x log(states) >= log(buckets)

        return (int) Math.ceil(Math.log(buckets) / Math.log(states));

    }

}

一刷

反正我自己是想不出来

这里的round -> n 表示的是n进制
譬如如果时间只够试一次
那么就是二进制，因为有 0, 1 表示喝和不喝
        如果有1只猪，能表示两个bucket
        如果有2只猪，bucket1 -> 00, bucket2 -> 01, bucket3 -> 10, bucket4 -> 11 根据猪死的情况可以decode出bucket的number
Conclusion: If we have x pigs, we could use them to represent (encode) 2^x buckets.

如果能够试两次
那么有 0, 1, 2分别表示没喝，round1喝, round2喝
       pigs -> buckets
        1    ->  0, 1, 2  -> 3        
        2    ->  00, 01, 02, 10, 11, 12, 20, 21, 22  -> 9 
        3    -> 000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101...
pigs -> bits
each bit has (round) states
all cases ->  pigs^states

4.50 % 
class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        // 0 is not drink, i is drink at ith round -> 0...i states
        int states = minutesToTest / minutesToDie + 1;
        // pigs^states >= buckets
        // log(buckets, states) <= pigs
        return (int)Math.ceil(Math.log(buckets) / Math.log(states));
    }
}