1 題目描述

2 解題思路

令 zeta(x) 為 x! 末尾零的個(gè)數(shù)。如果 x! 可以分解為素?cái)?shù)的乘積，如的形式，那么 x! 末尾零的個(gè)數(shù)為 min(a, b) = b。

zeta(x) 就是 x 除以 5 的次數(shù)之和，即 zeta(x) 等于

可以看出，zeta(x) 是一個(gè)單調(diào)遞增函數(shù)，因此可以使用二分查找求解。

使用二分查找找出滿足 zeta(x) = K 的最大 x 和最小 x

由于一定存在 zeta(5a-1) < zeta(5a) = zeta(5a+1) = zeta(5a+2) = zeta(5a+3) = zeta(5a+4) < zeta(5a+5)，即如果存在某個(gè) x 使得 zeta(x) = K，那么一定存在連續(xù) 5 個(gè)數(shù)的階乘末尾零的個(gè)數(shù)都為 K；如果不存在這樣的 x，那么階乘末尾零的個(gè)數(shù)為 K 的數(shù)字只有 0 個(gè)。

class Solution(object):def preimageSizeFZF(self, K):def zeta(x):if(x==0):return 0else:return x//5 + zeta(x//5) lo, hi = 4*K, 5*K + 1while lo < hi:mi = (lo + hi) // 2zmi = zeta(mi)if zmi == K: return 5elif zmi < K: lo = mi + 1else: hi = mireturn 0 #最終沒有找到這個(gè)數(shù)

接下來解釋一下這邊二分查找的時(shí)候的左邊界和右邊界是怎么找的：

我們可以得到

即x≥4k

即x≤5k

復(fù)雜度分析

時(shí)間復(fù)雜度：，二分查找的復(fù)雜度為 O(log K)，其中每一步計(jì)算 zeta 的復(fù)雜度也為 O(logK)。

空間復(fù)雜度：O(logK)，zeta 遞歸調(diào)用棧的大小。

總結(jié)

以上是生活随笔為你收集整理的文巾解题 793. 阶乘函数后 K 个零的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。