Number of trailing zeros of N!

2018-04-09  本文已影响10人  Tiny_z

这个题目的要求是,给定一个数字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
}
上一篇下一篇

猜你喜欢

热点阅读