Programa Golang para contar ceros finales en factorial de un número

Dado un entero n, escriba un programa Go para contar el número de ceros finales en el factorial de n. Ejemplos:

Input : 7
Output : 1
Explanation: 7! = 5040, which has 1 trailing zero

Input : 10
Output : 2
Explanation: 10! = 3628800, which has 2 trailing zeros

Enfoque ingenuo: para contar los ceros finales en n!, un enfoque es encontrar el factorial de n y luego contar el número de ceros finales usando un ciclo y contando el número de (n%10==0). Sin embargo, incluso para números pequeños como 20, el valor factorial es lo suficientemente grande como para causar un desbordamiento de enteros. Enfoque eficiente: para contar el número de ceros finales, primero se requiere comprender qué contribuye a los ceros finales en el factorial de un número. El número 10 es responsable de los ceros finales. La descomposición en factores primos de 10 es 2*5. En la descomposición en factores primos de cualquier número, el número de 2 siempre es mayor o igual que el número de 5. Por lo tanto, solo se requiere encontrar el número de cincos en la factorización prima del número. Ejemplo 1:Cuando n = 7, la descomposición en factores primos de 7! es 2^4 * 3^2 * 5^1 * 7^1. El número de 5 en la descomposición en factores primos es 1. Por lo tanto, ¡el número de ceros finales en 7! es 1. Ejemplo 2: Cuando n = 10, la descomposición en factores primos de 10! es 2^8 * 3^4 * 5^2 * 7^1. El número de 5 en la descomposición en factores primos es 2. Por lo tanto, ¡el número de ceros finales en 10! es 2

trailingZerosCount = piso (n/5) + piso (n/5 ^ 2) + piso (n/5 ^ 3) + …. + piso (n/5^k) donde 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, the loop
  // calculates floor(n/5) + floor(n/25) +
  // floor(n/125) + ..... until 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))
}

Producción:

The number of trailing zeros in 10! is 2

Complejidad de tiempo : O (log n) ya que los bucles se ejecutarán durante los tiempos de inicio de sesión