Interview Classic 150 Problem P172 Factorial Trailing Zeroes

---

Timeline

Timeline

2025-11-26

init

Math

---

Problem:

P172 Factorial Trailing Zeroes

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

10 is made up of 2 × 5, and in the factorial n! there are always more 2s, making 5 the limiting factor. Trailing zeros are because the end has:

$$10 = 2 × 5$$

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

• There are many even numbers → the number of factor 2s is huge
• But numbers that provide 5 are few (only 5, 10, 15, 20, 25 …)

Because the distribution of numbers containing 5 is:

• Every 5 numbers, there is 1 number containing one 5 (e.g., 5, 10, 15, 20)
• Every 25 numbers, there is 1 number containing an “extra 5” (e.g., 25, 50, 75)
• Every 125 numbers, there is one containing “one more 5”, and so on
  …

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