創作內容

0 GP

LeetCode - 172. Factorial Trailing Zeroes 解題心得

作者:Not In My Back Yard│2020-09-02 00:00:22│巴幣:0│人氣:116
題目連結:


題目意譯:
給定一整數 n,回傳 n! 末尾的 0 之數量。

注:你的解答應為對數時間複雜度。



範例測資:
範例 1:
輸入: 3
輸出: 0
解釋: 3! = 6 , 沒有末尾的 0 。

範例 2:
輸入: 5
輸出: 1
解釋: 5! = 120 , 有一個末尾 0 。


解題思維:
可以看到每個 0 的出現,同時代表著 n! 裡有著一個 10 的乘積。

而因為 10 = 2 × 5 且 2 < 5 ,因此在 n! 中,是 2 的倍數的數字肯定比 5 的倍數的數字來得多。

因此只要看 n! 中有多少個「5」,就可以知道有多少個「10」,即是「0」的數量。

而「5」在乘積中的次方可由下求出:
先計算 floor(n ÷ 5) 的值,代表 5 的倍數有多少個。這些數字各自貢獻一個「5」的次方。
再計算 floor(n ÷ 25) 的值,代表 25 的倍數有多少個。這些數字除了像 5 的倍數貢獻一個次方以外,還會再貢獻另一個次方。
再來計算 floor(n ÷ 125) 的值,代表 125 的倍數有多少個。這些數字除了像 25 的倍數貢獻兩個次方以外,還會再貢獻另一個次方。
……
以此類推。其中 floor 函式代表下高斯函數,對於非負整數來說等同無條件捨去小數點。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4902756
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|數學

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊切換新版閱覽

作品資料夾

Airsoftotaku大家
Merryy最新的V少女連動漫畫"世界級的災難"翻譯好囉看更多我要大聲說2小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】