Question: https://leetcode.com/problems/factorial-trailing-zeroes/
Question Name: Factorial Trailing Zeroes
I firstly saw this question on CTCI. The key points of the solution are:
- Every interger could be represented as (2^i)*(5^j)*x, where i, j >= 0 and x cannot be evenly divided by 2 or 5, according to prime decomposition.
- Every tailing zero comes from a pair of 2 AND 5. Therefore, the number of tailing zeroes is the number of pairs of 2 and 5.
- For all integers, in form of (2^i)*(5^j)*x, i >= j. In other words, the number of pairs of 2 and 5 is determined by the number of j (min(i, j) = j). As a result, the number of tailing zeroes is j for the factorial result.
Then the question turn to be: after prime decomposition on n!, what is the exponent for base 5.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution: # @param {integer} n # @return {integer} def _numOfFiveInFactorial(self, n): result = 0 while n != 0: result += n // 5 n //= 5 return result # @param {integer} n # @return {integer} def trailingZeroes(self, n): return self._numOfFiveInFactorial(abs(n)) |