Solution to Factorial Trailing Zeroes by LeetCode

24 Apr

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:

  1. 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.
  2. 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.
  3. 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.


Leave a Reply

Your email address will not be published. Required fields are marked *