[Leetcode] 793. Preimage Size of Factorial Zeroes Function 解题报告

题目：

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].

思路：

通过数学知识我们可以知道，f(x)后面有多少个零，取决于在[1, x]区间内的所有数中，一共有多少个5的因数（5， 10各算一个，25算有两个5的因数，125算3个，以此类推）。而我们发现，f(x)其实是单调的阶跃函数，如下图所示：

所以给定一个K，我们需要做的就是在横坐标上找到对应的X区间。可以发现，如果K落在上图所示的水平区域内，那么满足f(x) = K的x的个数就是5；否则就是0，例如上图所示的K从4到6的跳跃，对应于x从24到25。这样我们就可以采用二分查找的方法，确定x究竟处在哪个区域，从而判断满足f(x) = K的个数到底是5还是0。

代码：

class Solution {
public:
    int preimageSizeFZF(int K) {
        long left = 0, right = 5L * (K + 1);
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long num = numOfTrailingZeros(mid);
            if (num < K) {
                left = mid + 1;
            } 
            else if (num > K) {
                right = mid - 1;
            } 
            else {
                return 5;
            }
        }
        return 0;
    }
private:
    long numOfTrailingZeros(long x) {
        long res = 0;
        for (; x > 0; x /= 5) {
            res += x/5;
        }
        return res;
    }
};