题目

描述

给定一个非负整数 NN，返回 N!N! 结果的末尾为 00 的数量。
N!N! 是指自然数 NN 的阶乘,即:。

方法一

思路

• 题目要求计算阶乘末尾0的数量，最直接的方法就是通过计算n!，得出其值，然后在逐个的找出末尾的0，得出末尾0的数量；
• 考虑到N的范围比较大，使用long会溢出，所以采用Java中BigDecimal来进行阶乘的运算；
• 得出阶乘的结果后，再将数值转换成字符串，从尾部开始遍历，找出末尾所有的零。
• 代码如下：

  import java.util.*;
  import java.math.BigDecimal;
  public class Solution {
    /**
     * the number of 0
     * @param n long长整型 the number
     * @return long长整型
     */
    public long thenumberof0 (long n) {
        // 使用BigDecimal来存储乘积
        BigDecimal multi = new BigDecimal(String.valueOf(1));
        // 实现阶乘运算
        while(n > 1){
            BigDecimal bb = new BigDecimal(String.valueOf(n));  
            multi = multi.multiply(bb);
            --n;
        }
        // 找出末尾零的的个数
        int count = 0;
        String str = String.valueOf(multi);
        for (int i = str.length()-1;i >= 0;--i){
            if (str.charAt(i) != '0'){
                break;
            }
            ++count;
        }
        return count;
    }
  }

• 时间复杂度：，计算阶乘需要，BigDecimal乘法的时间复杂度为，分别为两个数的长度；
• 空间复杂度：，由于最后会将阶乘值转换成字符串，所以需要阶乘值的长度的空间，关于阶乘值存在如下计算公式（斯特林公式）：；而对于一个十进制数X的长度则存在如下计算公式：。

方法二

思路

• 由于N的范围比较大，所以采用方法一可能会导致程序运行超时，无法啊完美解决问题，需要考虑降低时间复杂度，从而提高程序运行速度；
  
  
  
  

• 观察10以内的数字的互乘，可以发现只有2 * 5 = 10会产生0，也就是说两个数相乘会产生0，则这两个数中必有因子5和2，且5的个数一定是小于2的个数的，所以要找出一个阶乘n!末尾0的数量，只需要找出从1~n这n个数中总共有多少个因子5；

• 但是，从1遍历到n每个数看一下它能除多少次5是不行的。因为n的数据范围是1e18，遍历1e18个数运行时间过大。

• 其实存在如下公式：5的数量count = n/5+n/25+……+n/5+……;

• 那么这公式是什么意思呢？n/5即阶乘中所有至少含有一个因子5的个数，而n/25即阶乘中所有至少含有两个因子5的个数，由于在n/5中已经统计一次n/25了，所以只需要在加一次n/25即可，以此类推，从而得出n的阶乘中因子5的个数。

• 故可以依据此公式进行计算末尾0的数量。

• 代码如下：

  import java.util.*;
  import java.math.BigDecimal;
  public class Solution {
    /**
     * the number of 0
     * @param n long长整型 the number
     * @return long长整型
     */
    public long thenumberof0 (long n) {
  
        long count = 0;
        long base = 5;
        while(n >= base){
            count = count + n / base;
            base *= 5;
        }
        return count;
    }
  }

• 时间复杂度：，从0~n遍历；

• 空间复杂度：，常数级空间复杂度。