Golang 计算尾部0的阶乘程序

给定一个整数n，编写一个Go程序来计算n的阶乘中的尾部零的个数。

举例：

输入： 7
输出： 1
解释：7！=5040，其中有1个尾随零。

输入： 10
输出： 2
解释：10！=3628800，其中有2个尾随零

Naive approach: 计算n！的尾随零，做法之一是找到n的阶乘，然后使用循环和计算（n％10==0）的数量来计算其尾随零的数量。 然而，即使对于像20这样的小数字，阶乘的值也足以引起整数溢出。

package main
 
import "fmt"
 
// countZeros function counts the number of trailing zeros in the factorial of n using a naive approach
func countZeros(n int) int {
    count := 0
    for i := 1; i <= n; i++ {
        j := i
        for j%5 == 0 {
            count++
            j /= 5
        }
    }
    return count
}
 
func main() {
    n := 10
    fmt.Printf("Count of trailing 0s in %d! is %d\n", n, countZeros(n))
} 

输出:

Count of trailing 0s in 10! is 2

时间复杂度： O(n^2)

Efficient Approach: 要计数尾随零的数量，首先需要了解是什么造成了数字的阶乘中的尾随零。数字10负责尾随零。 10的质因数分解是2 * 5。 在任何数字的质因数分解中，2的数量始终大于或等于5的数量。 因此，只需要在数字的质因数分解中找到5的数量即可。

例子1： 当n = 7时，7！的质因数分解为2 ^ 4 * 3 ^ 2 * 5 ^ 1 * 7 ^ 1。质因数分解中5的数量为1。因此，7！的尾随零的数量为1。

例子2： 当n = 10时，10！的质因数分解为2 ^ 8 * 3 ^ 4 * 5 ^ 2 * 7 ^ 1。质因数分解中5的数量为2。因此，10！的尾随零的数量为2。

trailingZerosCount = floor(n/5) + floor(n/5^2) + floor(n/5^3) + …. + floor(n/5^k) where 5^k <= n

// Golang Program to Count Trailing
// Zeros in Factorial of a Number
package main
 
import (
  "fmt"
)
 
func trailingZeros(n int) int {
 
  // This function return the number of
  // trailing zeros in the factorial of
  // a number n.
  // The count variable denotes the
  // number of trailing zeros in n!
  count := 0
   
  // This loop counts the number
  // of occurrences of 5 and its
  // powers in n!
  // Starting with p = 5,循环计算floor(n/5)+floor(n/25)+floor(n/125)+ ….. 直到n/p>0
  for p := 5; n/p > 0; p *= 5 {
    count += n / p
  }
  return count
}
 
// Driver code
func main() {
  n := 10
  fmt.Printf("The number of trailing zeros"+
    " in %v! is %v", n, trailingZeros(n))
} 

输出：

The number of trailing zeros in 10! is 2

时间复杂度 : O(log n)，因为循环会执行log n次

Auxiliary Space : O(1)，因为使用的是常量空间