How to calculate number of trailing zeroes in given factorial

user_18231682 0
Viewed 113

I am using below code for calculating trailing zeroes. It passes sample inputs, but it fails testcases. Can someone please point out the mistake in the code, so that I do not repeat it.

t = int(input())
#taking input for number of test cases
for i in range(t):
    n = int(input())
    i = 1 
    lis = []
    while 5**i < n:
        lis.append((n//(5**i)))
        i += 1 
    print(sum(lis))

Following was sample input: 6 3 60 100 1024 23456 8735373

And it did return correct answers.

I have now realised what I had done wrong, in line 7, I wrote while 5**i < n: instead I shoud have wrote while 5**i <= n:

Only test cases where above code fails are 5^i. This was my first question on stack overful, I am quite delighted by helpfulness of the community.

factorial python
1 Answers

The idea is good, but for exact powers of 5 it will go wrong.

For example n=25. As this has two factors of 5 (it is 5²), there is an extra trailing zero: while 24! has 4 trailing zeroes, 25! has 6 trailing zeroes. For each factor of 5 there is an extra zero. So similarly, 125! will have three zeroes more than 124! has.

So you need to include that exponent when 5**i == n also. Note that there is no need for a list.

You could use this function:

# Returns the number of trailing zeroes in the 
# decimal representation of n! (the factorial of n)
def get_trailing_zeroes(n):
    zeroes = 0 
    while n > 0:
        n //= 5
        zeroes += n
    return zeroes
user_54598390
Related