172. Factorial Trailing Zeroes - python3

Given an integer n, return the number of trailing zeroes in n!.

Follow up: Could you write a solution that works in logarithmic time complexity?

오랜만에 다시 돌아온 알고리즘 ~~~..........!!

My Answer 1: Time Limit Exceeded (500 / 500 test cases passed, but took too long.)

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        factorial = 1
        for i in range(1, n+1):
            factorial *= i
        while factorial%10 == 0:
            count += 1
            factorial = factorial//10
        return count

맨 처음 생각한 건 역시..^^
먼저 팩토리얼을 구하고 10 으로 나눈 나머지를 이용해서 0 의 개수를 셈

그래서 직접 팩토리얼을 계산해본 결과
뭔가 n 에 포함된 5 의 개수에 따라서 0 의 개수가 결정되는 거 같음
ex) 5! => 1개 / 10! => 2개 / 25! => 6개 (25 는 5 가 2 개임)

My Answer 2: Accepted (Runtime: 28 ms - 87.12% / Memory Usage: 14.1 MB - 53.91%)

class Solution:
    def trailingZeroes(self, n: int) -> int:
        if n < 5:
            return 0
        count = 0
        while n:
            count += n // 5
            n = n // 5
        return count

중간에 삽질이 좀 있었지만...
(그냥 5 로 계속 나누면 되는데 1 부터 n 까지의 수들을 5로 나눠서 1 개씩 더하고.. 암튼 노답이었음)

결론은 n 을 계속 5로 나눠서 5 의 개수를 세면 된다!!!