LeetCode - Factorial Trailing Zeros

https://leetcode.com/problems/factorial-trailing-zeroes/

It’s an easy problem using some basic math.

The question asks to count number of trailing zeroes of N! = 1.2.3…N

Solution:

The trailing zero come from 10 in a product, to count number of 10 in a product, we simply count number of 2 and 5 factors in this product.

N! = (1) * (2) * (3) * (22) * (5) * (23) * ….

We can easily see that number of 5 is less than number of 2 in N!, so our task is count the number of 5-factor.

One notice is that, in N! there are some number which has more than 1 5-factor which is k5^x (for example 25 = 55, 50 = 255). We have to count all of them

  1. This is the first solution

We continuously count the number from 1→N where this number is divisible by 5^x

1
2
3
4
5
6
7
8
9
func trailingZeroes(n int) int {
cnt := 0
v := 5
for v <= n {
cnt += n/v
v *= 5
}
return cnt
}

We can notice a “smelly code” in this solution.

What is this? This is v *= 5 . Why? Because v can larger than MAX_INT, the overflow can be happened. That why i came up with the second solution.

2. Second solution

1
2
3
4
5
6
7
8
func trailingZeroes(n int) int {
cnt := 0
for n > 0 {
cnt += n/5
n /= 5
}
return cnt
}

With this solution, you don’t have to deal with overflow.

Time complexity O(log5(N))

Support me via: https://ko-fi.com/iamquang95