LeetCode 172:Factorial Trailing Zeroes

LeetCode 172:Factorial Trailing Zeroes

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

//題目描述：給定一個整數n，返回n!（n的階乘）數字中的後綴0的個數。
//方法一：先求得n的階乘，然後計算末尾0的個數，這種方法當n比較大是，n!會溢出
class Solution {
public:
	int trailingZeroes(int n) {
		if (n == 0) return 0;
		int m = 0;
		int cnt = 0;
		int k = factorial(n);
		while (k){
			m = k % 10;
			k = k / 10;
			if (m == 0)	
				cnt++;
			else
				break;
		}
		return cnt;
	}

	//計算n的階乘
	int factorial(int n1){
		if (n1 == 0) return 1;
		else{
			return n1*factorial(n1 - 1);
		}
	}
};

//方法二：考慮n!的質數因子。後綴0總是由質因子2和質因子5相乘得來的，如果我們可以計數2和5的個數，問題就解決了。
//考慮例子：n = 5時，5!的質因子中(2 * 2 * 2 * 3 * 5)包含一個5和三個2。因而後綴0的個數是1。
//n = 11時，11!的質因子中((2 ^ 8) * (3 ^ 4) * (5 ^ 2) * 7)包含兩個5和八個2。於是後綴0的個數就是2。
//我們很容易觀察到質因子中2的個數總是大於等於5的個數,因此只要計數5的個數即可。
//那麼怎樣計算n!的質因子中所有5的個數呢？一個簡單的方法是計算floor(n / 5)。例如，7!有一個5，10!有兩個5。
//除此之外，還有一件事情要考慮。諸如25，125之類的數字有不止一個5。
//例如n=25, n!=25*24*23*...*15...*10...*5...*1=(5*5)*24*23*...*(5*3)*...(5*2)*...(5*1)*...*1，其中25可看成5*5,多了一個5，應該加上
//處理這個問題也很簡單，首先對n÷5，移除所有的單個5，然後÷25，移除額外的5，以此類推。下面是歸納出的計算後綴0的公式。
//n!後綴0的個數 = n!質因子中5的個數= floor(n / 5) + floor(n / 25) + floor(n / 125) + ....

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