LeetCode 793 Preimage Size of Factorial Zeroes Function
概述
https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/
Hard 哦。
二分搜索
首先,n! 的个末尾零的个数是知道的:
int trailingZeroes(int n) {
int count = 0;
int c = n;
while (c / 5 != 0) {
count += c / 5;
c /= 5;
}
return count;
}
详见:https://iamazing.cn/page/leetcode-172-factorial-trailing-zeroes
显然该函数递增,那么就可以用二分查找求区间。
https://labuladong.gitee.io/algo/4/30/119/
先求左边界,再求右边界,最后算下差就好了。
属于是有些麻烦了。
O(logn * logn)
下面代码 WA(24 / 44 test cases passed),不想 debug 了,我好累:
class Solution {
public:
int preimageSizeFZF(int k) {
// find left bound
long l = 0, r = LLONG_MAX;
while (l < r) {
long m = (r - l) / 2 + l;
if (trailingZeroes(m) >= k) {
r = m;
} else {
l = m + 1;
}
}
long leftBound = l;
// find right bound
l = 0, r = LLONG_MAX;
while (l < r) {
long m = (r - l) / 2 + l;
if (trailingZeroes(m) <= k) {
l = m + 1;
} else {
r = m;
}
}
long rightBound = l;
return rightBound - leftBound;
}
int trailingZeroes(long n) {
int count = 0;
long c = n;
while (c / 5 != 0) {
count += c / 5;
c /= 5;
}
return count;
}
};
Links: leetcode-793-preimage-size-of-factorial-zeroes-function