793. Preimage Size of Factorial Zeroes Function
793. Preimage Size of Factorial Zeroes Function
题目: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/
难度: Hard
题意：
- 求n!末尾有k个0的n有多少个
思路：
- 因式分解，末尾有0肯定是2*5，不管n是多大，n!分解因式后，2的个数肯定比5的个数多
- 假设给定n，如何求n!分解因式后有多少个5？每隔5个数贡献一个5因子，每隔25个数有多贡献一个5因子。。。统计能得到结果
- 这个题的做法是二分一个范围区间，求出n!分解因式后因子5的个数等于k的上下界，相减所得
- 这个题有个可优化的点，答案要么是0，要么是5，因为每隔5个数肯定会贡献一个5因子。那么我们只需要一个二分，找出是否有一个n，分解因式后有k个5因子，就可以返回5，否则返回0
解法：
class Solution {
private long cal5(long n) {
long ret = 0;
while (n != 0) {
ret += n / 5;
n /= 5;
}
return ret;
}
private long upper(long left, long right, int k) {
while (right - left > 1) {
long mid = (left + right) / 2;
if (cal5(mid) <= k) {
left = mid;
} else {
right = mid;
}
}
if (cal5(left) == k) {
return left;
} else {
return -1;
}
}
private long lower(long left, long right, int k) {
while (right - left > 1) {
long mid = (left + right) / 2;
if (cal5(mid) >= k) {
right = mid;
} else {
left = mid;
}
}
if (cal5(right) == k) {
return right;
} else {
return -1;
}
}
public int preimageSizeFZF(int K) {
long n = upper(1, 6000000000L, K);
if (n == -1) {
return 0;
} else {
long m = lower(-1, n, K);
return (int) (n - m + 1);
}
}
}
