美文网首页
Number of trailing zeros of N!

Number of trailing zeros of N!

作者: Tiny_z | 来源:发表于2018-04-09 10:05 被阅读10次

    这个题目的要求是,给定一个数字n,然后返回n的阶乘的尾数0的长度

    一开始想准备用阶乘算出总和,然后通过切割结果,取最后数组的长度,代码如下

    function zeros(n){
              var res = 1
              while(n > 0){
                res *= n;
                n--;
              }
              return ('' + res).replace(/[^0]/g,' ').split(' ').pop().length;
              
            }
    
            console.log(zeros(12)) // 2
    

    但是这个方法没法计算大数,大数阶乘后会超过取值范围,直接返回次幂的形式 zeros(40) // res-> 8.15915283247898e+47
    这种形式就走不通了

    下面是另外一种方法,我们想得到末位是0的数字,一定就是需要2*5的。
    但是因子2一般是要多余因子5的,我们就可以直接用5来做因子
    如何计算n的因子总数为5的数量呢?

    Math.floor(n/5)
    但还有一种情况,像25,125这种数字,不止一个5
    例如,n=28 这里会多出一个5, 这时0的数量为6
    所以,我们首先将n除以5,可以除去单个的5,然后除以25,这次就可以除去多余的5,依次类推,得到公式如下
    count = Math.floor(n/5) + Math.floor(n/25) + floor(n/125) + ....

    最终的代码如下:

    function zeros (n) {
      let count = 0;
      for(let i = 5; n/i >= 1; i*= 5){
        count += Math.floor(n/i)
      }
      return count
    }
    

    相关文章

      网友评论

          本文标题:Number of trailing zeros of N!

          本文链接:https://www.haomeiwen.com/subject/ejubhftx.html