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的數的個數。暴力法是首先求出n!，然後直接計算末尾0的個數。（重復(n!)/10，直到余數非0為止），若輸入的n 值過大時，在計算階乘時會導致溢出，因此該方法並不好用。

http://www.cnblogs.com/ganganloveu/p/4193373.html 給出一種很巧妙的解決方法：

事實上，只要對n的階乘n!，做因數分解：n!=2^x*3^y*5^z*...

顯然0的個數等於min(x,z)，並且經證明，可以得到：min(x,z)==z 。

例如：

n = 5時，5!的質因數分解：5! = 2 * 2 * 2 * 3 * 5 中包含3個2、1個3和1個2。後綴0的個數是1。

n = 11時，11!的質因數分解：11! = 2^8 * 3^4 * 5^2 * 7 中包含8個2、4個3和2個5。後綴0的個數是2。

證明：

對於階乘而言，也就是1*2*3*...*n，設[n/k]代表1~n中能被k整除的個數
顯然有，[n/2] > [n/5] (左邊是逢2增1，右邊是逢5增1)
[n/2^2] > [n/5^2](左邊是逢4增1，右邊是逢25增1)
……
[n/2^p] > [n/5^p](左邊是逢2^p增1，右邊是逢5^p增1)
隨著冪次p的上升，出現2^p的概率會遠大於出現5^p的概率。
因此左邊的加和一定大於右邊的加和，也就是n!質因數分解中，2的次冪一定大於5的次冪。

三.示例代碼

#include 
using namespace std;

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

四.小結

這道題的代碼很少，但是要從題目中把復雜的要求轉化為簡單的運算是需要推導的，總體來說還是需要費一定的功夫。