I am trying to calculate the number of trailing zeros in a factorial.
def count(x):
zeros = 0
for i in range (2,x+1):
print(i)
if x > 0:
if i % 5 == 0:
print("count")
zeros +=1
else:
("False")
print(zeros)
count(30)
I think the number of trailing zeros is incorrect.
When using count(30), there are 7 trailing 0‘s in 30. However it is returning 6.
6
def count (x):
i = 5
zeros = 0
while x >= i:
zeros += x // i
i *= 5
return zeros
print(count(30))
3
Wikipedia has a short article on this specific topic, which says that this can be computed with a straight-forward summation that counts factors of 5.
def trailing_zeros_of_factorial(n):
assert n >= 0, n
zeros = 0
q = n
while q:
q //= 5
zeros += q
return zeros
# 32! = 263130836933693530167218012160000000
print(trailing_zeros_of_factorial(32)) # => 7
We would first count the number of multiples of 5 between 1 and n (which is X ), then the number of multiples of 25 ( ~s ), then 125, and so on.
To count how many multiples of mare in n, we can just divide n by m
def countFactZeros(num):
count = 0
i = 5
if num < 0:
return False
while num//i > 0:
count = count + num//i
i = i * 5
return count
countFactZeros(10) # output should be 2
countFactZeros(100) # output should be 24
Your algorithm has problem:
import math
def count_zeroes(x):
zeroes = 0
if x <= 0:
return zeroes
for i in range(5, x+1, 5):
for base in range(int(math.log(i, 5)), 0, -1):
if i % pow(5, base) == 0:
zeroes += base
break
return zeroes
1
Try the following:
def zeros(n):
x = n/5
return x+zeros(x) if x else 0