Hard

题目描述

设 f(x) 为 x! 末尾零的数量。回顾 x! = 1 * 2 * 3 * ... * x，按照惯例，0! = 1。

例如，f(3) = 0，因为 3! = 6 的末尾没有零，而 f(11) = 2，因为 11! = 39916800 的末尾有两个零。

给定一个整数 k，返回具有 f(x) = k 性质的非负整数 x 的数量。

示例 1：

输入：k = 0
输出：5
解释：0!、1!、2!、3! 和 4! 的末尾都有 k = 0 个零。

示例 2：

输入：k = 5
输出：0
解释：不存在 x 使得 x! 的末尾有 k = 5 个零。

示例 3：

输入：k = 3
输出：5

提示：

  • 0 <= k <= 10^9

解题思路

这道题需要理解阶乘末尾零的来源：每个零都由因子 2 和 5 相乘产生，由于因子 2 的数量总是比因子 5 多，所以零的个数等于因子 5 的个数。

对于 n!，其中因子 5 的个数为：n/5 + n/25 + n/125 + ...

关键观察：

  1. 函数 f(x) 是单调递增的
  2. 对于任意 k，要么存在 5 个连续的 x 值使得 f(x) = k，要么不存在任何 x 使得 f(x) = k

这是因为在区间 [5^i, 5^i + 4] 中，f(x) 的值相同，每增加 5 个数，f(x) 至少增加 1。

解法思路：

  1. 使用二分查找找到最小的 x 使得 f(x) >= k
  2. 如果 f(x) = k，则存在 5 个这样的 x（因为 f 在每个长度为 5 的区间内保持常数）
  3. 如果 f(x) > k，则不存在任何 x 使得 f(x) = k

时间复杂度为 O(log²k)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int preimageSizeFZF(int k) {
        // 计算 n! 中尾部零的个数
        auto countZeros = [](long long n) -> long long {
            long long count = 0;
            while (n > 0) {
                n /= 5;
                count += n;
            }
            return count;
        };
        
        // 二分查找第一个使得 f(x) >= k 的 x
        long long left = 0, right = 5LL * k;
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (countZeros(mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 检查找到的 x 是否满足 f(x) = k
        return countZeros(left) == k ? 5 : 0;
    }
};

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def count_zeros(n):
            """计算 n! 中尾部零的个数"""
            count = 0
            while n > 0:
                n //= 5
                count += n
            return count
        
        # 二分查找第一个使得 f(x) >= k 的 x
        left, right = 0, 5 * k
        
        while left < right:
            mid = (left + right) // 2
            if count_zeros(mid) < k:
                left = mid + 1
            else:
                right = mid
        
        # 检查找到的 x 是否满足 f(x) = k
        return 5 if count_zeros(left) == k else 0

public class Solution {
    public int PreimageSizeFZF(int k) {
        // 计算 n! 中尾部零的个数
        long CountZeros(long n) {
            long count = 0;
            while (n > 0) {
                n /= 5;
                count += n;
            }
            return count;
        }
        
        // 二分查找第一个使得 f(x) >= k 的 x
        long left = 0, right = 5L * k;
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (CountZeros(mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 检查找到的 x 是否满足 f(x) = k
        return CountZeros(left) == k ? 5 : 0;
    }
}

var preimageSizeFZF = function(k) {
    function trailingZeroes(n) {
        let count = 0;
        while (n >= 5) {
            n = Math.floor(n / 5);
            count += n;
        }
        return count;
    }
    
    function findFirst(k) {
        let left = 0, right = 5 * k + 1;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (trailingZeroes(mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    function findLast(k) {
        let left = 0, right = 5 * k + 1;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (trailingZeroes(mid) <= k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }
    
    let first = findFirst(k);
    if (trailingZeroes(first) !== k) {
        return 0;
    }
    let last = findLast(k);
    return last - first + 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(log²k)，二分查找的复杂度为 O(log k)，每次计算零的个数的复杂度为 O(log k)
空间复杂度O(1)，只使用常数额外空间

相关题目