階乘很簡單？恕我直言，階乘相關的面試題你還真不一定懂！

對于如何算 n 的階乘，隻要你知道階乘的定義，我想你都知道怎麼算，但如果在面試中，面試官抛給你一道與階乘相關，看似簡單的算法題，你還真不一定能夠給出優雅的答案！本文将分享幾道與階乘相關的案例，且難度遞增。

給定一個整數 N，那麼 N 的階乘 N! 末尾有多少個 0？例如： N = 10，則 N！= 3628800，那麼 N! 的末尾有兩個0。

有些人心想，這還不簡單，直接算出 N！的值，然後用除以 10 來判斷多少個 0 就可以了。

有些人則這樣想，直接算 N！的值再來除以 10 判斷多少個 0 的話肯定會出現溢出問題，于是開始思索：一個數乘以 10 就一定會在末尾産生一個零，于是，我們可以從“哪些數相乘能夠得到 10 ”入手。

沒錯，隻有 2 * 5 才會産生 10。

注意，4 5 = 20 也能産生 0 啊，不過我們也可以把 20 進行分解啊，20 = 10 2。

于是，問題轉化為 N! 種能夠分解成多少對 25，再一步分析會發現，在 N！中能夠被 2 整除的數一定比能夠被 5 整除的數多，于是問題就轉化為求 1…n 這 n 個數中能夠被 5 整除的數有多少個，注意，像 25 能夠被 5整除兩次，是以25是能夠産生 2 對 2 5滴。有了這個思路，代碼如下：

有些人想出了這個規律，很是得意，然而，這還不是面試官要的答案，大家想一個問題，

當 N = 20 時，1~20 可以産生幾個 5 ？答是 4 個，此時有 N / 5 = 4。

當 N = 24 時，1~24 可以産生幾個 5 ？答是 4 個，此時有 N / 5 = 4。

當 N = 25 時，1~25 可以産生幾個 5？答是 6 個，主要是因為 25 貢獻了兩個 5，此時有 N / 5 + N / 5^2 = 6。

…

可以發現 産生 5 的個數為 sum = N/5 + N/5^2 + N/5^3+….

于是，最優雅的寫法應該是這樣：

這時，你就可以自信這把代碼扔給面試官了。

求 N! 的二進制表示中最低位 1 的位置。例如 3！=6，二進制為 1010，是以 最低位 1 的位置在第二位。 沒有思路？請仔細想一下這道題與上道題的關系！

仔細想一下，這道題不也是求末尾有多少個 0 嗎？你求出了末尾有多少個0自然知道 1 的位置（0的個數加1就是1的位置了），隻不過，這道題是求二進制末尾有多少個 0。

由于是二進制，是以每次乘以 2 末尾就會産生一個 0 。

于是，模仿上面一道題，求 N！含有多少個 2 的個數。心想，幸好我做個類似了，于是一波操作猛如虎，一分鐘就寫出了代碼：

面試官：還能在優化嗎？

什麼鬼？還要在優化？我都 O(logn) 時間複雜度了。

還記得我之前講解了幾道有關位運算的嗎？這道題确實可以用位運算來優化，除以 n / 2 == n >> 1。不過位運算的速度快多了，于是，優化後的代碼如下：

還能在優化嗎？

可以，不過我先不講，因為我覺得，這已經夠快了。後面講其他題可能會把這道題再拿出來講。

如果你能寫出這樣的代碼，已經算很牛逼了。

給你一個數 N，輸出 N! 的值。

沒錯，就是這麼簡單，直接讓你求階乘的值。

這個時候，你就要小心了，千萬别一波操作

一個 for 循環，馬上搞定。

因為你不知道 n 的範圍，有可能你用 long long 也是會溢出的，是以這個時候應該要問一下面試官有沒有限定 n 的範圍。

面試官：沒有限定！

這下好了，這道階乘的題，難度頓時上升了，說實話，我敢保證大部分人還真沒去實作過。是以，今天我就帶大家來實作一下，以防以後真的被問到。結果最熟悉的題頓時不知道怎麼下手好。

這個時候，我們就必須用字元串來存放所求的值的，在相乘的時候也是用字元串來相乘，說白了，就是要會求兩個大整數相乘。

下面我們先來實作一個求兩個大整數相乘的函數。一種比較簡單的方法就是，像我們國小那會一樣，讓個位數與另一個數的其他數相乘，然後讓十位數與另一個的其他數相乘，最後在把他們進行相加。

實作代碼如下：

注意，一定要自己實作一遍，一定要自己實作一遍，因為原理簡單，但手動實作就不一定那麼簡單了，容易出現bug。

采用這種方法的話，兩個大整數相乘的時間複雜度為 O(n)，其實還有更快的方法，大概時間複雜度是 O(n^1.6)，不過代碼有點小複雜，感興趣的可以閱讀這篇文章：漫畫：如何實作大整數相乘？,我這裡就不展開說了，不然單獨這個就可以另起一篇很長的文章了。

知道了兩個大整數相乘之後，我們再來算我們的階乘，就好做了，我們每次相乘的時候，隻需要把它當作兩個大整數重複乘就可以了。代碼如下：

時間複雜度是 O(n^3)。如果要優化的話，主要是在大整數相乘這裡進行優化。

是不是覺得，階乘也沒有那麼簡單了？這三道與階乘相關的題，應該是比較常見的題吧，今天跟大家分享一波，希望大家有時間的話，自己也用代碼實作一下，特别是算 N!。後面會繼續跟大家分享一些我覺得不錯的算法題以及一些算法技巧，敬請關注。