Leetcode-172-阶乘后的0个数

Leecode-172-Factorial Trailing Zeroes

思路：数学题

题目描述

给定一个整数 n，返回 n! 结果尾数中零的数量。

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

你算法的时间复杂度应为 O(log n)

Solution：

• 首先肯定不能依赖于把阶乘算出来再去判断有多少个零了，因为阶乘很容易就溢出了，所以先一步一步理一下思路吧
• 首先末尾有多少个 0 ，只需要给当前数乘以一个 10 就可以加一个 0。
• 再具体对于 5!，也就是 5 * 4 * 3 * 2 * 1 = 120，我们发现结果会有一个 0，原因就是 2 和 5 相乘构成了一个 10。而对于 10 的话，其实也只有 2 * 5 可以构成，所以我们只需要找有多少对 2/5。

举个例子看一下：

11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1

• 对于含2的因子的是：1 * 2, 2 * 2, 3 * 2, 4 * 2 …

• 对于含5的因子的是：1 * 5, 2 * 5…

• 含2的因子每两个出现一次，含有5的因子每5个出现一次，所以2出现的个数远远多余5，换而言之，只需要找到一个5，那么一定会有一个2和他匹配。所以我们只需要找多少个5就好

  • 每隔 5 个数出现一个 5，所以计算出现了多少个 5，我们只需要用 n/5 就可以算出来。
  • 每隔 25 个数字，出现的是两个 5，所以除了每隔 5 个数算作一个 5，每隔 25 个数，还需要多算一个 5
  • 同理我们还会发现每隔 5 * 5 * 5 = 125个数字，会出现 3 个 5，所以我们还需要再加上 n / 125 。
  • 最终5的个数就是 n/5 + n/25 + n/125 ....

Java

写程序的话，如果按照上面的式子计算，分母很可能会溢出。所以计算n/25的时候，我们先把n更新，在n = n/5 ，然后再计算 n/5 即可。

Solution :

class Solution {
    public int trailingZeroes(int n) {
        // 记录5出现的个数
        int count = 0;
        // 计算阶乘中5的个数
        while (n > 0){
            // 5  出现一个 5
            // 25 出现两个 5
            // 125 出现三个 5
            // .....
            count += n/5;
            // 更新n
            n = n/5;
        }
        return count;
    }
}

Python

Solution :

打赏