Saturday, September 2, 2017

458. Poor Pigs

https://leetcode.com/problems/poor-pigs/description/
Solution. 
Consider an n-dimensional space, with m marks in each dimension. The total points in the space is m^n.
Let each pig represent 1 dimension. The maximum times a pig can check is T. In x direction, the pig can check all the points with x = 1, ..., T, respectively. If the pig dies after checking x = x1, the coordinate for the poison in this dimension is x = x1. If the pig is alive after checking x=T, the coordinate for the poison is x = T + 1. Thus, the maximum points that 1 pig can represent is m = T + 1. After the coordinate for each dimension is know, the poison can be located.
The points that n pigs can check is m^n.
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int m = minutesToTest / minutesToDie + 1;
        int pigs = 0;
        while( pow(m, pigs) < buckets ){
            pigs++;
        }
        return pigs;
    }
or,
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int m = minutesToTest / minutesToDie + 1;
        return ceil(log(buckets)/log(m));
    }

No comments:

Post a Comment