(LeetCode) 172. Factorial Trailing Zeroes

172. Factorial Trailing Zeroes

• Explore : Interview > Top Interveiw Questions > Medium Collection
• 분류 : Math
• 난이도 : Easy

Problem

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?

Example 1

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3

Input: n = 0
Output: 0

Constraints

• 0 <= n <= 10^4

Solution

Exapnder

class Solution {
    fun trailingZeroes(n: Int): Int {
        var number = n
        var result = 0
        while (number > 0) {
            result += number /5
            number /= 5
        }
        return result
    }
}

Point of Thinking

• 팩토리얼에서 끝에 붙은 0의 개수를 찾는 문제이다.
• 팩토리얼의 결과값의 끝이 0이 되는 조합은 단 하나 뿐이다. 2 * 5 = 10
• 즉, 주어진 n을 5로 계속 나누어서 카운팅하면 되는데 25와 같은 5^2도 처리해주어야 한다.
• 규칙성을 찾아보면 아래와 같다.

n	factorial	value	trailingZeroes
1	1!	1	0
2	2!	2	0
3	3!	6	0
4	4!	24	0
5	5!	120	1
6	6!	720	1
7	7!	5040	1
8	8!	40320	1
9	9!	362880	1
10	10!	3628800	2
15	15!	1307674368000	3
20	20!	2432902008176640000	4
25	25!	15511210043330985984000000	6
30	30!	265252859812191058636308480000000	7