labuladong 的算法小抄 > 第三章、必知必会算法技巧 > 数学运算技巧 > 讲两道常考的阶乘算法题

讲两道常考的阶乘算法题

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
172. Factorial Trailing Zeroes	172. 阶乘后的零	🟠
793. Preimage Size of Factorial Zeroes Function	793. 阶乘函数后 K 个零	🔴

———–

笔试题中经常看到阶乘相关的题目，今天说两个最常见的题目：

1、输入一个非负整数 n，请你计算阶乘 n! 的结果末尾有几个 0。

这也是力扣第 172 题「阶乘后的零」，比如说输入 n = 5，算法返回 1，因为 5! = 120，末尾有一个 0。

函数签名如下：

int trailingZeroes(int n);

2、输入一个非负整数 K，请你计算有多少个 n，满足 n! 的结果末尾恰好有 K 个 0。

这也是力扣第 793 题「阶乘后 K 个零」，比如说输入 K = 1，算法返回 5，因为 5!,6!,7!,8!,9! 这 5 个阶乘的结果最后只有一个 0，即有 5 个 n 满足条件。

函数签名如下：

int preimageSizeFZF(int K);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int preimageSizeFZF(int K);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def preimageSizeFZF(K: int) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func preimageSizeFZF(K int) int {
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var preimageSizeFZF = function(K) {

我把这两个题放在一起，肯定是因为它们有共性，下面我们来逐一分析。

题目一

肯定不可能真去把 n! 的结果算出来，阶乘增长可是比指数增长都恐怖，趁早死了这条心吧。

那么，结果的末尾的 0 从哪里来的？我们有没有投机取巧的方法计算出来？

首先，两个数相乘结果末尾有 0，一定是因为两个数中有因子 2 和 5，因为 10 = 2 x 5。

也就是说，问题转化为：n! 最多可以分解出多少个因子 2 和 5？

比如说 n = 25，那么 25! 最多可以分解出几个 2 和 5 相乘？这个主要取决于能分解出几个因子 5，因为每个偶数都能分解出因子 2，因子 2 肯定比因子 5 多得多。

25! 中 5 可以提供一个，10 可以提供一个，15 可以提供一个，20 可以提供一个，25 可以提供两个，总共有 6 个因子 5，所以 25! 的结果末尾就有 6 个 0。

现在，问题转化为：n! 最多可以分解出多少个因子 5？

难点在于像 25，50，125 这样的数，可以提供不止一个因子 5，怎么才能不漏掉呢？

这样，我们假设 n = 125，来算一算 125! 的结果末尾有几个 0：

首先，125 / 5 = 25，这一步就是计算有多少个像 5，15，20，25 这些 5 的倍数，它们一定可以提供一个因子 5。

但是，这些足够吗？刚才说了，像 25，50，75 这些 25 的倍数，可以提供两个因子 5，那么我们再计算出 125! 中有 125 / 25 = 5 个 25 的倍数，它们每人可以额外再提供一个因子 5。

够了吗？我们发现 125 = 5 x 5 x 5，像 125，250 这些 125 的倍数，可以提供 3 个因子 5，那么我们还得再计算出 125! 中有 125 / 125 = 1 个 125 的倍数，它还可以额外再提供一个因子 5。

这下应该够了，125! 最多可以分解出 25 + 5 + 1 = 31 个因子 5，也就是说阶乘结果的末尾有 31 个 0。

理解了这个思路，就可以理解解法代码了：

class Solution {
    int trailingZeroes(int n) {
        int res = 0;
        long divisor = 5;
        while (divisor <= n) {
            res += n / divisor;
            divisor *= 5;
        }
        return res;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        long divisor = 5;
        while (divisor <= n) {
            res += n / divisor;
            divisor *= 5;
        }
        return res;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution:
    def trailingZeroes(self, n: int) -> int:
        res = 0
        divisor = 5
        while divisor <= n:
            res += n // divisor
            divisor *= 5
        return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func trailingZeroes(n int) int {
    res := 0
    divisor := 5
    for divisor <= n {
        res += n / divisor
        divisor *= 5
    }
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var trailingZeroes = function(n) {
    let res = 0;
    let divisor = 5;
    while (divisor <= n) {
        res += Math.floor(n / divisor);
        divisor *= 5;
    }
    return res;
};

🥳 代码可视化动画 🥳

这里 divisor 变量使用 long 型，因为假如 n 比较大，考虑 while 循环的结束条件，divisor 可能出现整型溢出。

上述代码可以改写地更简单一些：

class Solution {
    int trailingZeroes(int n) {
        int res = 0;
        for (int d = n; d / 5 > 0; d = d / 5) {
            res += d / 5;
        }
        return res;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        for (int d = n; d / 5 > 0; d = d / 5) {
            res += d / 5;
        }
        return res;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution:
    def trailingZeroes(self, n: int) -> int:
        res = 0
        for d in range(n, 0, -1):
            num_fives = 0
            while d % 5 == 0:
                num_fives += 1
                d //= 5
            res += num_fives
        return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func trailingZeroes(n int) int {
    res := 0
    for d := n; d/5 > 0; d = d / 5 {
        res += d / 5
    }
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var trailingZeroes = function(n) {
    var res = 0;
    for (var d = n; d / 5 > 0; d = Math.floor(d / 5)) {
        res += Math.floor(d / 5);
    }
    return res;
}

这样，这道题就解决了，时间复杂度是底数为 5 的对数，也就是 O(logN)，我们看看下如何基于这道题的解法完成下一道题目。

第二题

现在是给你一个非负整数 K，问你有多少个 n，使得 n! 结果末尾有 K 个 0。

一个直观地暴力解法就是穷举呗，因为随着 n 的增加，n! 肯定是递增的，trailingZeroes(n!) 肯定也是递增的，伪码逻辑如下：

int res = 0;
for (int n = 0; n < +inf; n++) {
    if (trailingZeroes(n) < K) {
        continue;
    }
    if (trailingZeroes(n) > K) {
        break;
    }
    if (trailingZeroes(n) == K) {
        res++;
    }
}
return res;

前文二分查找如何运用说过，对于这种具有单调性的函数，用 for 循环遍历，可以用二分查找进行降维打击，对吧？

搜索有多少个 n 满足 trailingZeroes(n) == K，其实就是在问，满足条件的 n 最小是多少，最大是多少，最大值和最小值一减，就可以算出来有多少个 n 满足条件了，对吧？那不就是二分查找中「搜索左侧边界」和「搜索右侧边界」这两个事儿嘛？

先不急写代码，因为二分查找需要给一个搜索区间，也就是上界和下界，上述伪码中 n 的下界显然是 0，但上界是 +inf，这个正无穷应该如何表示出来呢？

首先，数学上的正无穷肯定是无法编程表示出来的，我们一般的方法是用一个非常大的值，大到这个值一定不会被取到。比如说 int 类型的最大值 INT_MAX（2^31 - 1，大约 31 亿），还不够的话就 long 类型的最大值 LONG_MAX（2^63 - 1，这个值就大到离谱了）。

那么我怎么知道需要多大才能「一定不会被取到」呢？这就需要认真读题，看看题目给的数据范围有多大。

这道题目实际上给了限制，K 是在 [0, 10^9] 区间内的整数，也就是说，trailingZeroes(n) 的结果最多可以达到 10^9。

然后我们可以反推，当 trailingZeroes(n) 结果为 10^9 时，n 为多少？这个不需要你精确计算出来，你只要找到一个数 hi，使得 trailingZeroes(hi) 比 10^9 大，就可以把 hi 当做正无穷，作为搜索区间的上界。

刚才说了，trailingZeroes 函数是单调函数，那我们就可以猜，先算一下 trailingZeroes(INT_MAX) 的结果，比 10^9 小一些，那再用 LONG_MAX 算一下，远超 10^9 了，所以 LONG_MAX 可以作为搜索的上界。

注意为了避免整型溢出的问题，trailingZeroes 函数需要把所有数据类型改成 long：

// 逻辑不变，数据类型全部改成 long
long trailingZeroes(long n) {
    long res = 0;
    for (long d = n; d / 5 > 0; d = d / 5) {
        res += d / 5;
    }
    return res;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 逻辑不变，数据类型全部改成 long
long trailingZeroes(long n) {
    long res = 0;
    for (long d = n; d / 5 > 0; d = d / 5) {
        res += d / 5;
    }
    return res;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

# 逻辑不变，数据类型全部改成 long
def trailingZeroes(n: int) -> int:
    # 初始化结果
    res = 0
    d = n
    # 每个 5 可以贡献一个 0
    while d // 5 > 0:
        d /= 5
        res += d
    return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 逻辑不变，数据类型全部改成 int64
func trailingZeroes(n int64) int64 {
    var res int64 = 0
    for d := n; d / 5 > 0; d = d / 5 {
        res += d / 5
    }
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 逻辑不变，数据类型全部改成 long
var trailingZeroes = function(n) {
    var res = 0;
    for (var d = n; d / 5 > 0; d = Math.floor(d / 5)) {
        res += Math.floor(d / 5);
    }
    return res;
};

现在就明确了问题：

在区间 [0, LONG_MAX] 中寻找满足 trailingZeroes(n) == K 的左侧边界和右侧边界。

根据前文二分查找算法框架，可以直接把搜索左侧边界和右侧边界的框架 copy 过来：

class Solution {
    /* 主函数 */
    public int preimageSizeFZF(int K) {
        // 左边界和右边界之差 + 1 就是答案
        return (int)(right_bound(K) - left_bound(K) + 1);
    }

    /* 搜索 trailingZeroes(n) == K 的左侧边界 */
    long left_bound(int target) {
        long lo = 0, hi = Long.MAX_VALUE;
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (trailingZeroes(mid) < target) {
                lo = mid + 1;
            } else if (trailingZeroes(mid) > target) {
                hi = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    /* 搜索 trailingZeroes(n) == K 的右侧边界 */
    long right_bound(int target) {
        long lo = 0, hi = Long.MAX_VALUE;
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (trailingZeroes(mid) < target) {
                lo = mid + 1;
            } else if (trailingZeroes(mid) > target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo - 1;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    /* 主函数 */
    int preimageSizeFZF(int K) {
        // 左边界和右边界之差 + 1 就是答案
        return (int)(right_bound(K) - left_bound(K) + 1);
    }

    /* 搜索 trailingZeroes(n) == K 的左侧边界 */
    long left_bound(int target) {
        long lo = 0, hi = LONG_MAX;
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (trailingZeroes(mid) < target) {
                lo = mid + 1;
            } else if (trailingZeroes(mid) > target) {
                hi = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    /* 搜索 trailingZeroes(n) == K 的右侧边界 */
    long right_bound(int target) {
        long lo = 0, hi = LONG_MAX;
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (trailingZeroes(mid) < target) {
                lo = mid + 1;
            } else if (trailingZeroes(mid) > target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo - 1;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution:
    def preimageSizeFZF(self, K: int) -> int:
        # 左边界和右边界之差 + 1 就是答案
        return int(self.right_bound(K) - self.left_bound(K) + 1)
    
    # 搜索 trailingZeroes(n) == K 的左侧边界
    def left_bound(self, target: int) -> int:
        lo, hi = 0, float('inf')
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if self.trailingZeroes(mid) < target:
                lo = mid + 1
            elif self.trailingZeroes(mid) > target:
                hi = mid
            else:
                hi = mid
        return lo
    
    # 搜索 trailingZeroes(n) == K 的右侧边界
    def right_bound(self, target: int) -> int:
        lo, hi = 0, float('inf')
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if self.trailingZeroes(mid) < target:
                lo = mid + 1
            elif self.trailingZeroes(mid) > target:
                hi = mid
            else:
                lo = mid + 1
        return lo - 1

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func preimageSizeFZF(K int) int {
    /* 搜索 trailingZeroes(n) == K 的左侧边界 */
    left_bound := func(target int) int64 {
        lo, hi := int64(0), math.MaxInt64 // math.MaxInt64 is equivalent to Long.MAX_VALUE in Java
        for lo < hi {
            mid := lo + (hi-lo)/2
            if trailingZeroes(mid) < target {
                lo = mid + 1
            } else if trailingZeroes(mid) > target {
                hi = mid
            } else {
                hi = mid
            }
        }
        return lo
    }

    /* 搜索 trailingZeroes(n) == K 的右侧边界 */
    right_bound := func(target int) int64 {
        lo, hi := int64(0), math.MaxInt64 // math.MaxInt64 is equivalent to Long.MAX_VALUE in Java
        for lo < hi {
            mid := lo + (hi-lo)/2
            if trailingZeroes(mid) < target {
                lo = mid + 1
            } else if trailingZeroes(mid) > target {
                hi = mid
            } else {
                lo = mid + 1
            }
        }
        return lo - 1
    }

    // 左边界和右边界之差 + 1 就是答案
    return int(right_bound(K) - left_bound(K) + 1)
}

func trailingZeroes(n int64) int {
    res := 0
    for n > 0 {
        n /= 5
        res += int(n)
    }
    return res
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/**
 * @param {number} K
 * @return {number}
 */

// 主函数
var preimageSizeFZF = function(K) {
    // 左边界和右边界之差 + 1 就是答案
    return right_bound(K) - left_bound(K) + 1;
}

// 搜索 trailingZeroes(n) == K 的左侧边界
let left_bound = function(target) {
    let lo = 0, hi = Number.MAX_VALUE;
    while (lo < hi) {
        let mid = lo + Math.floor((hi - lo) / 2);
        if (trailingZeroes(mid) < target) {
            lo = mid + 1;
        } else if (trailingZeroes(mid) > target) {
            hi = mid;
        } else {
            hi = mid;
        }
    }
    return lo;
}

// 搜索 trailingZeroes(n) == K 的右侧边界
let right_bound = function(target) {
    let lo = 0, hi = Number.MAX_VALUE;
    while (lo < hi) {
        let mid = lo + Math.floor((hi - lo) / 2);
        if (trailingZeroes(mid) < target) {
            lo = mid + 1;
        } else if (trailingZeroes(mid) > target) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo - 1;
}

如果对二分查找的框架有任何疑问，建议好好复习一下前文二分查找算法框架，这里就不展开了。

现在，这道题基本上就解决了，我们来分析一下它的时间复杂度吧。

时间复杂度主要是二分搜索，从数值上来说 LONG_MAX 是 2^63 - 1，大得离谱，但是二分搜索是对数级的复杂度，log(LONG_MAX) 是一个常数；每次二分的时候都会调用一次 trailingZeroes 函数，复杂度 O(logK)；所以总体的时间复杂度就是 O(logK)。

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释