Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
solve.c

README.md

Factorial Trailing Zeroes

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

Note: Your solution should be in logarithmic time complexity.

Credits:

Special thanks to @ts for adding this problem and creating all test cases.

Solution

自然数相乘(0 除外), 只有当因子2 和 5相乘时才会有结尾0产生,比如20 * 5 = 2 * 5 * 2 * 5, 有两个2 * 5, 因此末尾有两个0.

阶乘计算时,自然数连续相乘,只需要统计有多少2 * 5,即可求出多少个末尾0, 而2的个数大于5的个数,因此最后只决定于有多少个5.

比如10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 2^8 * 3^4 * 5^2,由于5的因子数为2,因此10!末尾有2个0

我们知道5,10,15,20产生一个5因子,即每间隔5产生一个5因子,而25产生2个5因子,即每个25又会多一个5因子,因此25!共可产生6个5因子。

因此要计算阶乘N的5的因子个数,先统计每隔5产生因子,其值等于N / 5, 接下来计算每隔25产生的因子,个数应该为N / 25, 而由于前面已经除了5,因此 只需要N / 5即可. 依次类推,直到没有5因子产生.:w

Code

int trailingZeroes(int n)
{
	if (n < 0)
		return 0;
	int sum = 0;
	while (n) {
		sum += n / 5;
		n /= 5;
	}
	return sum;
}
You can’t perform that action at this time.