Interview Classic 150 Questions P172 Factorial Trailing Zeroes

---

Timeline

timeline

2025-11-26

init

math

---

Title:

P172 Factorial Trailing Zeroes

https://leetcode.cn/problems/factorial-trailing-zeroes/description/?envType=study-plan-v2&envId=top-interview-150

10 is composed of 2 × 5, and in factorial n!, the number of 2’s is always more, making 5 the limiting factor. Trailing zeros are because at the end there are:

$$10 = 2 × 5$$

So the number of trailing zeros in n! depends on how many pairs (2, 5) there are. But in n!:

• There are many even numbers → the number of factors of 2 is extremely large
• But numbers that can provide 5 are very few (only 5, 10, 15, 20, 25 …)

Because the distribution of numbers containing 5 is:

• Every 5 numbers, one appears that contains one 5 (e.g., 5, 10, 15, 20)
• Every 25 numbers, one appears that contains an ‘extra 5’ (e.g., 25, 50, 75)
• Every 125 occurrences contain ‘one more 5’, etc.
  …

class Solution {
    public:
	int trailingZeroes(int n)
	{
		int cnt = 0;
		while (n > 0) {
			n /= 5;
			cnt += n;
		}
		return cnt;
	}
};