LeetCode -- Factorial Trailing Zeroes

LeetCode -- Factorial Trailing Zeroes

題目描述：


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


Note: Your solution should be in logarithmic time complexity.


給定整數n，找出小於n的數中，找出階乘末尾為0的數的個數。




本題如果分別求1!,2!...n!，根本無法通過測試數據。
規律為：對於數字m!∈(0,n] ，如果m!末尾為0，那麼必有1個因數為5和2。因此題目便轉化為：
統計(0,n]之間，5約數個數和。



 


實現代碼：

public class Solution {
    public int TrailingZeroes(int n) {
        var c = 0;
        var factor = 5;
		var end = int.MaxValue / 5;
        while(n >= factor && factor != int.MaxValue){
            c += n/factor;
			if(factor > end){
				factor = int.MaxValue;
			}
			else{
				factor *= 5;
			}
        }
		
		return c;
    }
}