[LeetCode]Factorial Trailing Zeroes

纯数学题，trailing zero永远来自于2 * 5，而2的数量永远比5多，因为对于k * 5^n，k*2^n一定比他小，并且可以提供足够多的2使得5全部变为0，所以我们就需要求n分解质因数之后5的数量。假设n为50，我们先除以5，得10，至少有10个5。商为10，我们继续除以5，得2。代表除此之外还有25 = 5*5和50=2*5*5的两个5。那么我们只需要不停地对n除以5，得到每一次5为因数的数量，直到n为0即可。时间复杂度O(log n)，代码如下：

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

view raw Factorial Trailing Zeroes.cpp hosted with ❤ by GitHub