'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List



class Solution:
    # counting factors of 5, one liner
    # each 0 on the end of the factorial represents a multiplication by 10
    # 2 is always abundant, 5 is fewer, compared to 2
    '''
    the key idea is count how many 5's are in the factorial.
    So first we add n/5.
    Wait, we are missing 5X5, 2X5X5..., so we add n/25 (why not count as 
    two 5's for each , because one is already counted in n/5).
    Wait, we are missing 5X5X5, 2X5X5X5..., so we add n/125.
    Thus, count = n/5 + n/25 + n/125 + ... + 0
    '''
    def trailingZeroes1(self, n: int) -> int:
        return 0 if n == 0 else n // 5 + self.trailingZeroes(n // 5)
    
    
    # advanced, T: O(logn); S: O(1)
    def trailingZeroes3(self, n: int) -> int:
        zero_count = 0
        while n > 0:
            n //= 5
            zero_count += n
        return zero_count
    
    
    # intuitive version of counting 5
    # T: O(N), S: O(1)
    def trailingZeroes2(self, n: int) -> int:
        zero_count = 0
        for i in range(5, n + 1, 5):
            current = i
            while current % 5 == 0:
                zero_count += 1
                current //= 5
    
        return zero_count
    
    
    # TLE: recursion 
    def trailingZeroes(self, n: int) -> int:
        def frac(n):
            if n == 1:
                return 1
            else:
                return n*frac(n-1)
        
        pro = frac(n)
        res = 0
        for c in str(pro)[::-1]:
            if c == "0":
                res += 1
        return res

