(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

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

Example 2

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

Example 3

1
2
Input: n = 0
Output: 0

Constraints

  • 0 <= n <= 10^4

Solution

Exapnder
1
2
3
4
5
6
7
8
9
10
11
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