Ceros finales de un factorial
La misión
Problema
Dado un número entero no negativo n, indica cuántos ceros hay al final del factorial de n. El factorial en sí es astronómicamente grande incluso para un n modesto, así que calcularlo y luego contar caracteres no es una opción.
Ejemplos
Input: n = 5
Output: 1
Por qué: 120 termina en un solo cero
Input: n = 30
Output: 7
Input: n = 0
Output: 0
Por qué: caso límite: 0! es 1 y no tiene ceros finales
Pistas
0 / 3
Un cero final es lo que deja un factor diez, así que cuenta factores diez en lugar de dígitos.
Diez es dos por cinco, y los números del 1 al n aportan muchos más doses que cincos, así que uno de los dos siempre es el cuello de botella.
Cuenta cuántos de los valores hasta n son múltiplos de cinco, luego cuántos son múltiplos de veinticinco, luego de ciento veinticinco, y así sucesivamente. Cada potencia mayor aporta un cinco extra, y la suma de esos conteos es la respuesta.
- Tiempo objetivo
- O(log n)
- Espacio objetivo
- O(1)
Restricciones
- n ≥ 0
Solución
Cada cero final viene de un factor diez, y diez es un dos por un cinco. Entre uno y n siempre hay más números pares que múltiplos de cinco, así que los cincos se agotan primero y el conteo de cincos es la respuesta. Los múltiplos de cinco aportan uno cada uno, los múltiplos de veinticinco aportan un segundo, y así sucesivamente subiendo por las potencias, que es exactamente lo que suma el bucle. El tiempo es O(log n) porque la potencia se multiplica por cinco en cada ronda, y el espacio es O(1).
def trailing_zeros(n):
zeros, power = 0, 5
while power <= n:
zeros += n // power # every multiple of this power gives one more five
power *= 5 # 5, 25, 125 ... each adds a spare five
return zeros
print(trailing_zeros(5)) # -> 1
print(trailing_zeros(30)) # -> 7
print(trailing_zeros(0)) # -> 0
print(trailing_zeros(100)) # -> 24¿Lo que te frena es la idea y no el código? La criba de Eratóstenes lo explica.