题目

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 的数量。

示例：

输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。

输入：k = 5
输出：0
解释：没有匹配到这样的 x!，符合 k = 5 的条件。

输入: k = 3
输出: 5

解答 & 代码

本题要找能满足 f(x) = k 的非负整数 x 的数量，那么久可以通过二分查找满足 f(x) = k 的非负整数 x 的左、右边界：

二分查找的下界 left 初始化为 0
二分查找的上界 right 初始化为 LONG_MAX：因为本题 k 的范围是：，而 INT_MAX 的阶乘的尾随零个数小于，因此，需要将 right 初始化为 LONG_MAX

因此，本题的数据类型都改为 long

二分查找的判定条件，即 mid 的阶乘结果的尾随零个数和目标值 k 的关系

求 mid 的阶乘中尾随零的个数，见：

[中等] 172. 阶乘后的零

class Solution {
private:
    // 返回 n 的阶乘结果的尾随零个数
    long trailingZeroes(long n)
    {
        long result = 0;
        long div = 5;
        while(div <= n)
        {
            result += n / div;
            div *= 5;
        }
        return result;
    }
public:
    int preimageSizeFZF(int k) {
        // 1. 二分查找 trailingZeroes(n) == k 的左边界
        long left = 0;
        long right = LONG_MAX;
        long leftBoundary = -1;
        while(left <= right)
        {
            long mid = left + (right - left) / 2;
            long zeroCnt = trailingZeroes(mid);
            if(zeroCnt == k)
            {
                leftBoundary = mid;
                right = mid - 1;
            }
            else if(zeroCnt > k)
                right = mid - 1;
            else
                left = mid + 1;
        }
        // 如果不存在左边界，即不存在 trailingZeroes(n) == k，直接返回 0
        if(leftBoundary == -1)
            return 0;
        // 2. 二分查找 trailingZeroes(n) == k 的右边界
        left = 0;
        right = LONG_MAX;
        long rightBoundary = LONG_MAX;
        while(left <= right)
        {
            long mid = left + (right - left) / 2;
            long zeroCnt = trailingZeroes(mid);
            if(zeroCnt == k)
            {
                rightBoundary = mid;
                left = mid + 1;
            }
            else if(zeroCnt > k)
                right = mid - 1;
            else
                left = mid + 1;
        }
        // cout << "k = " << k << ", leftBoundary = " << leftBoundary << ", rightBoundary = " << rightBoundary << endl;
        // 3. 返回右边界 - 左边界 + 1
        return (int)(rightBoundary - leftBoundary + 1);
    }
};

复杂度分析：

时间复杂度 O(logK)：二分查找的事件复杂度 O(LONG_MAX) 是一个常数；每次二分调用函数 trailingZeroes(mid) 时间复杂度~O(logK)
空间复杂度 O(1)：

执行结果：

执行结果：通过
执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了 39.03% 的用户

hot 100

[困难] 793. 阶乘函数后 K 个零

题目

解答 & 代码