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
- This is the first solution
We continuously count the number from 1→N where this number is divisible by 5^x
1 | func trailingZeroes(n int) int { |
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 | func trailingZeroes(n int) int { |
With this solution, you don’t have to deal with overflow.
Time complexity O(log5(N))
Support me via: https://ko-fi.com/iamquang95