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;
};

参考资料