LeetCode（172）：階乘後的零 Factorial Trailing Zeroes（Java）

2019.9.5 #程式員筆試必備# LeetCode 從零單刷個人筆記整理（持續更新）

這道題可以用一行代碼直接搞定：

return (n/5)+(n/25)+(n/125)+(n/625)+(n/3125)+(n/15625)+(n/78125)+(n/390625)+(n/1953125)+(n/9765625)+(n/48828125)+(n/244140625)+(n/1220703125);
           

為什麼呢？觀察發現，階乘數中每包含m個5n的倍數，結果就會多出m*n個0。那麼結果運算隻要疊代找出有多少個5n的因子即可。

傳送門：階乘後的零

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

給定一個整數 n，傳回 n! 結果尾數中零的數量。

示例 1:
輸入: 3
輸出: 0
解釋: 3! = 6, 尾數中沒有零。

示例 2:
輸入: 5
輸出: 1
解釋: 5! = 120, 尾數中有 1 個零.

說明: 你算法的時間複雜度應為 O(log n) 。
           

/**
 *
 * Given an integer n, return the number of trailing zeroes in n!.
 * 給定一個整數 n，傳回 n! 結果尾數中零的數量。
 *
 */

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



           

#Coding一小時，Copying一秒鐘。留個言點個贊呗，謝謝你#