經典應用題 階乘的尾巴有幾個零 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