本文共 1502 字，大约阅读时间需要 5 分钟。

点击上方蓝字关注我，我们一起学编程

微信搜索：编程笔记本

进提案分享一道兆芯科技的笔试编程题：阶乘后的零。

题目描述：

给定一个整数 n，返回 n! 末尾零的数量。

1. 计算阶乘

int trailingZeroes(int n){
       int count = 0;    int factorial = 1;    // 存储阶乘结果    // 计算阶乘    while (n > 0) {
           factorial *= n--;    }    // 计算尾部的零数    while (factorial % 10 == 0) {
           ++count;        factorial /= 10;    }    return count;}

这种方法有两个问题：

• 第一个问题是计算阶乘十分耗时
• 第二个问题是保存阶乘结果的变量很容易溢出

微信搜索：编程笔记本

2. 计算因子5

我们发现，在 0~9 中，能够产生 0 的只有整十数以及 2*5。其中，“整十数”也可以分解成 “5” 与其他整数的乘积。

一个自然的想法时：**计算包含的因子 5 的数量。凑成2*5的数对，2 的数量比 5 的数量要多出很多，因此 5 的数量就是2*5**数对的数量。

int trailingZeroes(int n){
   	int five = 0;	for (int i = 1; i <= n; ++i) {
   		if (i % 5 == 0) {
   			++five;		}	}	return five;}

上面的代码段有一些问题：比方说，在数字 25 中，它可以分解成 5*5 ，相当于一个数贡献了两个 5 。所以我们需要对这种情况进行处理。

int trailingZeroes(int n){
   	int five = 0;	for (int i = 1; i <= n; ++i) {
   		int tmp = i;		while (tmp % 5 == 0) {
   		    ++five;			tmp /= 5;		}	}	return five;}

微信搜索：编程笔记本

一个小小的优化：

我们不需要从 1 开始，也不需要每次递增 1 ，因为非 5 的整倍数对数对的贡献为 0 。

int trailingZeroes(int n){
   	int five = 0;	for (int i = 5; i <= n; i += 5) {
   		int tmp = i;		while (tmp % 5 == 0) {
   		    ++five;			tmp /= 5;		}	}	return five;}

上面的程序段抽象成数学式子就是：

图

所以，一种更加高效的求解方法是：

int trailingZeroes(int n) {
       int count = 0;            while (n > 0) {
           count += n / 5;        n = n / 5;     }    return count;}

至此，这个问题就解决啦~

微信搜索：编程笔记本