Zeros finais de um fatorial
A missão
Problema
Dado um número inteiro não negativo n, informe quantos zeros existem no final de n fatorial. O próprio fatorial é astronomicamente grande mesmo para valores modestos de n, então calculá-lo e depois contar os caracteres não é uma opção.
Exemplos
Input: n = 5
Output: 1
Por quê: 120 termina em um único zero
Input: n = 30
Output: 7
Input: n = 0
Output: 0
Por quê: edge case: 0! é 1 e não tem nenhum zero final
Dicas
0 / 3
Um zero final é o que um fator dez deixa para trás, então conte fatores de dez, e não dígitos.
Dez é dois vezes cinco, e os números de 1 a n fornecem muito mais fatores dois do que fatores cinco, então um dos dois é sempre o gargalo.
Conte quantos valores até n são múltiplos de cinco, depois quantos são múltiplos de vinte e cinco, depois de cento e vinte e cinco, e assim por diante. Cada potência maior contribui com um cinco extra, e a soma dessas contagens é a resposta.
- Tempo-alvo
- O(log n)
- Espaço-alvo
- O(1)
Restrições
- n ≥ 0
Solução
Todo zero final vem de um fator dez, e dez é um dois vezes um cinco. Entre um e n sempre há mais números pares do que múltiplos de cinco, então os cincos acabam primeiro e a contagem de cincos é a resposta. Múltiplos de cinco contribuem com um cada, múltiplos de vinte e cinco contribuem com um segundo, e assim por diante, subindo pelas potências, que é exatamente o que o loop soma. O tempo é O(log n), porque a potência fica cinco vezes maior a cada rodada, e o espaço é 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)) # -> 24Travou na ideia, e não no código? Crivo de Eratóstenes explica isso.