# 74th LeetCode Weekly Contest Preimage Size of Factorial Zeroes Function

2018/03/06 19:25

Let `f(x)` be the number of zeroes at the end of `x!`. (Recall that `x! = 1 * 2 * 3 * ... * x`, and by convention, `0! = 1`.)

For example, `f(3) = 0` because 3! = 6 has no zeroes at the end, while `f(11) = 2` because 11! = 39916800 has 2 zeroes at the end. Given `K`, find how many non-negative integers `x` have the property that `f(x) = K`.

``````Example 1:
Input: K = 0
Output: 5
Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.

Example 2:
Input: K = 5
Output: 0
Explanation: There is no x such that x! ends in K = 5 zeroes.``````

Note:

• `K` will be an integer in the range `[0, 10^9]`.

``````class Solution
{
public:
int numOfZero(int n){
int num = 0, i;
for(i=5; i<=n; i*=5)
{
num += n/i;
}
return num;
}
map<int,int>Mp;
int preimageSizeFZF(int K){
int l=K,r=K*10+1;
while(l<r){
int mid=l+(r-l)/2;
if(numOfZero(mid)==K){
return 5;
}else if(numOfZero(mid)<K){
l=mid+1;
}else{
r=mid;
}
}
return 0;
}
};``````

0
0 收藏

### 作者的其它热门文章 0 评论
0 收藏
0 