經典應用題 階乘的尾巴有幾個零 Leetcode #172
題目敘述
題目會給定我們一個n值，問我們n! 也就是n階乘 尾巴的零有多少個?
例如n=5 就是代表5! = 5x4x3x2x1=120 尾巴有一個零，回傳1
測試範例
Example 1:
Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.
Example 2:
Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Example 3:
Input: n = 0
Output: 0
約束條件
Constraints:
0 <= n <= 104
Follow up: Could you write a solution that works in logarithmic time complexity?
演算法:
除了平鋪直敘，直接相乘的模擬法之外；還有一個比較高效率O( log n) 的數學分析演算法。
尾巴的零來自於乘以10有幾個? 相當於 乘以2乘以五幾次?
n! = n * n-1 * ... * 1 = 2^i * 5^j * 其他質因數
觀察階乘的規律可以知道，5出現的次數一定小於等於2出現的次數，所以零的數目由5的次方數決定。
若階乘中有5出現一次，則尾巴有一個零。
若階乘中有5出現兩次，則尾巴有兩個零。
...
若階乘中有5出現k次，則尾巴有k個零。
所以我們只要把n拿去除以五，數數看5出現幾次，就知道n!尾巴有幾個零。
程式碼
class Solution:
def trailingZeroes(self, n: int) -> int:
if n == 0:
# Base case
return 0
else:
# Inductive step
return ( n//5 + self.trailingZeroes(n//5) )
複雜度分析
時間複雜度:
O( log n )
n 反覆除以5，最多耗費O( log n ) 步可以降階到終止條件 n == 0。
空間複雜度:
O( log n )
n 反覆除以5，最多耗費O( log n ) 步可以降階到終止條件 n == 0。
也是遞迴函數呼叫stack最大深度。
關鍵知識點
在於觀察幾個小範例，發現n! 尾巴零的個數 = 乘以10 幾次 = x 2 x 5 幾次
=> 5出現的次數一定小於等於2出現的次數，所以零的數目由5的次方數決定。
Reference:
[1] Python/JS/Go/C++ solution with O( log N ) [w/ Hint] - Factorial Trailing Zeroes - LeetCode
