Faktöriyelin sondaki sıfırları
Görev tanımı
Problem
Negatif olmayan bir n tam sayısı verildiğinde, n faktöriyelin sonunda kaç sıfır durduğunu söyle. Faktöriyelin kendisi mütevazı n'ler için bile astronomik büyüklükte, bu yüzden onu hesaplayıp karakterleri saymak bir seçenek değil.
Örnekler
Input: n = 5
Output: 1
Neden: 120 tek bir sıfırla bitiyor
Input: n = 30
Output: 7
Input: n = 0
Output: 0
Neden: edge case: 0! 1'dir ve sonunda sıfır yoktur
İpuçları
0 / 3
Sondaki her sıfırı bir 10 çarpanı bırakır; yani basamakları değil, 10 çarpanlarını say.
On, iki çarpı beştir ve 1'den n'ye kadarki sayılar beşten çok daha fazla iki verir; yani ikisinden biri her zaman darboğazdır.
n'ye kadarki değerlerden kaçının beşin katı olduğunu, sonra kaçının yirmi beşin katı olduğunu, sonra yüz yirmi beşin ve böyle devam say. Her yüksek kuvvet fazladan bir beş katar ve bu sayıların toplamı cevaptır.
- Hedef zaman
- O(log n)
- Hedef alan
- O(1)
Kısıtlar
- n ≥ 0
Çözüm
Sondaki her sıfır bir on çarpanından gelir ve on, iki çarpı beştir. Bir ile n arasında her zaman beşin katlarından daha fazla çift sayı vardır; bu yüzden beşler önce tükenir ve beşlerin sayısı cevaptır. Beşin katları birer, yirmi beşin katları ikinci bir tane katar ve kuvvetler boyunca böyle devam eder; döngünün topladığı da tam olarak bu. Kuvvet her turda beş kat büyüdüğü için zaman O(log n), alan 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)) # -> 24Kodda değil de fikirde mi takıldın? Eratosthenes kalburu bunu anlatıyor.