172. Factorial Trailing Zeroes

Problem

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

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

Example 2:

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

Note: Your solution should be in logarithmic time complexity.

Problem Summary

Given an integer n, return the number of zeroes at the end of the result of n!. Note: The time complexity of your algorithm should be O(log n).

Solution Approach

• Given a number n, find the number of trailing 0s in n!.
• This is a math problem. To calculate how many trailing 0s N factorial has, compute how many 10s there are in N!, which is also computing how many 2s and 5s there are in N! (prime factorization). The final result is the smaller of the number of 2s and the number of 5s. Every two numbers adds one more prime factor 2, while every five numbers adds one more prime factor 5. Every 5 numbers adds one more prime factor 5. The factorials of 04 have no prime factor 5, the factorials of 59 have 1 prime factor 5, the factorials of 10~14 have 2 prime factors 5, and so on. Therefore, the number of 0s is min(number of 5s in the factorial and number of 2s).
• How many trailing 0s N! has is how many prime factors 5 N! has. How many prime factors 5 N! has is how many groups of 5 numbers N can be divided into, plus how many groups of 25 numbers it can be divided into, plus how many groups of 125 numbers it can be divided into, and so on. That is, res = N/5 + N/(5^2) + N/(5^3) + ... = ((N / 5) / 5) / 5 /... . The final algorithm complexity is O(logN).

Code

package leetcode

func trailingZeroes(n int) int {
	if n/5 == 0 {
		return 0
	}
	return n/5 + trailingZeroes(n/5)
}