[Top Interview 150 - Math] 172. Factorial Trailing Zeroes

[Q] [Medium]

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

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

 

• int -> list 바꾸는 과정이 필요했다.
• 0 만 따로 처리해주고, math.factorial 이용하면 쉬운 문제였다.
• 다만 n = 1574 였을 때 오류가 났는데 애초에 math.factorial 이 적용되지 않았다.
• 큰 수의 경우 이런식으로 구할 수 없음을 깨닫고 찾아보니 5의 배수가 뒷 자리 0을 가져온다는 것을 이용해야 했다. -> 5로 나눠서 몫을 계산하여 가져오면 뒷자리 0의 개수를 알 수 있다.
• 아직도 수학도 갈 길이 멀다.

# Wrong Answer

import math

class Solution:
    def trailingZeroes(self, n: int) -> int:
        
        # 0 처리
        if n == 0:
            count = 0

        else :
            # ! 계산하고
            ans = math.factorial(n)
            ans_list = list(str(ans))
            
            # 끝에서부터 0 세기
            count = 0
            ran = len(ans_list)

            for i in range(ran):
                if ans_list[-1] == '0' :
                    count += 1
                    del ans_list[-1]
                    ran -= 1
                else:
                    break

        return count

 

# Answer

class Solution:
    def trailingZeroes(self, n: int) -> int:
        
        count = 0

        while n:
            n //= 5
            count += n

        return count