题目:
f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x,且 0! = 1 。
例如, f(3) = 0 ,因为 3! = 6 的末尾没有 0 ;而 f(11) = 2 ,因为 11!= 39916800 末端有 2 个 0 。
给定 k,找出返回能满足 f(x) = k 的非负整数 x 的数量。
示例 1:
输入:k = 0
输出:5
解释:0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。
示例 2:
输入:k = 5
输出:0
解释:没有匹配到这样的 x!,符合 k = 5 的条件。
示例 3:
输入: k = 3
输出: 5
提示:
0 <= k <= 109
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
结果:
![](https://img-blog.csdnimg.cn/d87e55cb12b9482286ee4211b390c849.png)
解题思路:
我一开始想要把乘积算出来,然后很快就发现天真了。。。
于是取看了题解,感谢题解中【爪哇缪斯】图解LeetCode 这篇图解,根据他的题解就真的能够明白为什么。——>大佬题解
简单说下题解中的思路:
![](https://img-blog.csdnimg.cn/img_convert/89532a6c9dc2453f304626f0d6317647.png)
首先我们要确定的是,乘积是否多一个0出来,取决于5 和 2 组合的个数,(至于为什么。。。我不知道,反正看看规律就是这样)。因为2出现的次数太多,不利于计算,这里用5计算。因此我们乘积中出现多少个0,完全取决于5的个数。
![](https://img-blog.csdnimg.cn/img_convert/664af089ce96d55f63517c34eff59f1c.png)
由此可以看出我们出现的5的个数就是0的个数。
然后5*5, 5*5 * 5这种5的次方的值,因为其本身的值会被5整除,这样可能会误导我们个数的计算,因此这部分需要单独拿出来算1个5.。
![](https://img-blog.csdnimg.cn/img_convert/b6104328d6ec03fd2ae59f3c9642988d.png)
因此这题计算的k 如果存在一个 nums / 5 + nums / 25 + nums / 625 。。。的和,那就存在有k个0存在的场景。
最后,既然是一致计算5的个数,那就很容易明白,我们每5个数会多出至少1个0,所以我们返回的个数只可能是0 和 5.
最后注意:虽然不计算乘积,但是因为要和5做计算,会超出int范围!
代码:
// 由题解可以学习到,其实这道题就是求相乘的数字中出现5和5的倍数的个数
// 因此我们从start到end之间只需要保证5和5的倍数存在的个数和等于k存在那就存在5个。
int preimageSizeFZF(int k){
long long start = 0;
long long end = (long long)5 * k;
while(start <= end) {
long long sum = 0;
long long num = 5;
long long mid = (end - start)/2 + start;
while (num <= mid) {
sum += (mid / num); // 当前mid包含5的个数,5的倍数的个数的和。
num *= 5;
}
if (sum == k) {
// 说明5和5的倍数的个数之和为k,也就是可以存在有k个0存在的场景。
return 5;
} else if (sum < k) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return 0;
}