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