[LeetCode] 172. Factorial Trailing Zeroes* 解題思路 (Easy)

這題給一個 n ，然後做 n! 運算，需要算後面尾數有幾個 0。

LeetCode 題目連結

 

https://leetcode.com/problems/factorial-trailing-zeroes/

題目

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Accept 作法

這題時間複雜度 O(n)，難在要找出規律，發現數字裡面含有幾個 5 決定最後 0 的數量。
例如: 5!=120 有一個 0，25! 則含有 5, 10,15,20,25(5*5)，所以有六個 0。

原本我的作法是真的算有幾個 0，但是因為數字中間會有 0，沒辦法精準算結尾的 0，反而導致怎麼樣都是錯誤的。


Runtime: 0 ms
Memory: 36.3 MB

Java 程式碼

class Solution {
    public int trailingZeroes(int n) {
        int sum = 0;
        while(n > 0){
            sum += n/5;
            n/=5;
        }
        return sum;
    }
}

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題