主題

LeetCode - 793. Preimage Size of Factorial Zeroes Function 解題心得

Not In My Back Yard | 2021-09-16 00:00:05 | 巴幣 0 | 人氣 46

題目連結:


題目意譯:
定義 f(x) 為 x! 的末尾零之數量(回想一下,x! = 1 × 2 × …… × n ,且根據常規, 0! = 1)。

例如, f(3) = 0 因為 3! = 6 的結尾沒有任何的零 ,而 f(11) = 2 因為 11! = 39916800 有著 2 個零在結尾。給定 k ,請找到有多少非負整數 x 滿足 f(x) = k 。

注:
k 會是位於範圍 [0, 10 ^ 9] 中的整數。



範例測資:
範例 1:
輸入: k = 0
輸出: 5
解釋: 0! 、 1! 、 2! 、 3! 和 4! 以 k = 0 個零作結。

範例 2:
輸入: k = 5
輸出: 0
解釋: 沒有任何 x 值滿足 x! 以 k = 5 個零作結。


解題思維:
假設我們已經知道要怎麼計算 N! 末尾零的數量,即 f(N)(作法參見這題),則我們可以套用二分搜尋法(Binary Search)來找到最小的 x 值滿足 f(x) ≧ k 。

令下界 L = 0 、 上界 U = 5000000000 (上界大概定個值就好,在此 f(5000000000) = 1249999998 > 10 ^ 9)。接著重複以下步驟直到 L = U 為止:
令 M = floor((L + U) ÷ 2) ,其中 floor() 為下高斯函數,其對於正數為無條件捨去小數點。如果 f(M) < k ,則我們將下界提高為 L = M + 1 ;反之,將上界降低至 U = M 。

最後檢查 f(L) 是否等於 k 。如果不等於就代表著不存在任何 x 值滿足 f(x) = k ,因此回傳 0 ;反之, x = L 即是滿足 f(x) = k 的最小值,而 x = L + 1 、 L + 2 、 L + 3 、 L + 4 也都會符合 f(x) = k。因此回傳 5 即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作