[Golang]力扣Leetcode—中级算法—数学—阶乘后的零

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

提示 n! = n (n - 1) (n - 2) ... 3 2 1

链接： 力扣Leetcode—中级算法—数学—阶乘后的零.

示例 1:

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

示例 2：

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

示例 3：

输入：n = 0
输出：0

标签：数学

错误思路：大家一开始想到的方法大多是一边计算阶乘，一边计算零的个数的方法，但是这种方法就算不报错也会超时。就是当数n大了以后，可能会超出int类型的表示范围，可能会导致结果变为负数或者因溢出而造成的截断误差。

错误Go代码如下：

package main

import (
    "fmt"
)

func trailingZeroes(n int) int {
    if n <= 0 {
        return 0
    }
    res := 1
    for i := 1; i <= n; i++ {
        res *= i
    }
    sum := 0
    for res != 0 {
        a := res % 10
        if a == 0 {
            sum++
        } else {
            break
        }
        res /= 10
    }
    return sum
}

func main() {
    fmt.Println(trailingZeroes(30))
}

当输入为30时，当乘到22，res就变成了负数，导致错误：

正确思路：我们可以想在什么情况下乘积的末尾会是零，自然就是因数包含了类似于10这种自身带有0的数和类似于5这种自身包含5的数

• 当自身包含10的时候，我们只需要找出这个数中的10的个数即可
• 当自身包含5的时候，我们也只需要找出这个数中5的个数就可以了，为什么呢？因为5乘以一个偶数必然是包含一个0的，而在计算阶乘中，偶数的个数明显比包含的5的个数多，所以对于每一个5我们都默认能够找到一个偶数与之相乘
• 当自身同时包含10和5的时候，我们只需要找出里面10和5的个数就可以了，建议优先找10，当然优先找5也可以

全部Go代码：

package main

import (
    "fmt"
)

func trailingZeroes(n int) int {
    if n <= 0 {
        return 0
    }
    count := 0
    for i := 1; i <= n; i++ {
        number := i
        if number%5 == 0 {
            for {
                count++
                if number%10 == 0 {
                    number /= 10
                } else {
                    number /= 5
                }
                if number%5 != 0 {
                    break
                }
            }
        }
    }
    return count
}

func main() {
    fmt.Println(trailingZeroes(30))
}

提交截图：