172. Factorial Trailing Zeroes

Leetcode 問題: 172. Factorial Trailing Zeroes
Categories:
Tags:

題目

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

Note that n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1.

傳入一個整數 n 計算 n! 階層 的數字尾巴總共有幾個連續的 0

Example

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

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

Input: n = 0
Output: 0
階層 運算 數值
1! 1
2! 1*2 = 2
3! 123 = 6
4! 123*4 = 24
5! 12345 = 120
6! 12345*6 = 720
7! 1234567 = 5040
8! 1234567*8 = 40320
9! 123456789 = 362880
10! 123456789*10 = 3628800

演算法

1. 計算尾部 0 的次數

因為每 5!，尾部會出現 1 個 0，所以只要計算傳入的數字能夠被多少個 5 整除即可計算出 0 的個數

階層 尾部 0 個數
5! 1
10! 2
15! 3
20! 4
25! 5

2. 加上 5! 自己本身的 0

當等於 5 時，表示自己 5! 還有 1 個 0 需要再加上去

所以當計算因數要 大於等於 5 (>= 5) 才能停止運算

答案

JavaScript

function trailingZeroes(nFactorial) {
    // 尾數 0 出現次數
    var numberOfTrailingZeroCount = 0;
    while (nFactorial >= 5) {
        // 數字能被多少 5 整除，表示尾部有多少 0
        nFactorial = Math.floor(nFactorial / 5);
        // 加上 0 的出現次數
        numberOfTrailingZeroCount += nFactorial;
    }
    return numberOfTrailingZeroCount;
}

TypeScript

function trailingZeroes(nFactorial: number): number {
    // 尾數 0 出現次數
    let numberOfTrailingZeroCount = 0;

    while (nFactorial >= 5) {
        // 數字能被多少 5 整除，表示尾部有多少 0
        nFactorial = Math.floor(nFactorial / 5);
        // 加上 0 的出現次數
        numberOfTrailingZeroCount += nFactorial;
    }

    return numberOfTrailingZeroCount;
};

參考資料