LeetCode 172 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n – 1) * (n – 2) * … * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：

输入：n = 0
输出：0

提示：

• 0 <= n <= 10^4

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

解题：

func trailingZeroes(n int) int {
	r, c := 1, 0
	for n > 0 {
		r *= n
		for r%10 == 0 {
			r /= 10
			c++
		}
		r %= 10000
		n--
	}
	return c
}

官方解答：

1.数学

func trailingZeroes(n int) (ans int) {
	for i := 5; i <= n; i += 5 {
		for x := i; x%5 == 0; x /= 5 {
			ans++
		}
	}
	return
}

2.优化计算

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