Factorial Trailing Zeros

problem at: https://leetcode.com/problems/factorial-trailing-zeroes

# Solution

Brute force solution is to calculate and keep dividing by and count number of 's.

# Number of 5's

Factor a number: . We can see only has 1 trailing zero b/c the number of pair of and is 1.

For a factorial, the number of 2's is definitely more than that of 5's.

Thus, the number of 5's is the number of trailing zeros.

Complexity:

  • time:
  • space:
def trailingZeroes(self, n: int) -> int:
    cnt = 0
    while n>0:
        cnt += n//5
        n //= 5
    return cnt

or

def trailingZeroes(self, n: int) -> int:
    cnt = 0
    while n>0:
        n //= 5
        cnt += n
    return cnt