[LeetCode] 172. Factorial Trailing Zeroes

轉自LeetCode

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

Note: Your solution should be in logarithmic time complexity.

<Solution>
這題要找 N! 後面有多少個 0，也就是 10 的倍數

那 10 又可以分解為 2 * 5，而 2 這個因數在 2! 之後存在很多

所以數目受限於有幾個 5，因此算出 N 包含幾個 5 即可

code如下(參考資料)

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

view raw fractorialTrailingZeros.cpp hosted with ❤ by GitHub