46 - 阶乘后的零

题目

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

示例 1:

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

示例 2:

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

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

解答

首先想到的就是暴力法，算出阶乘的结果，然后判断一下最后一位是不是0

var factorial = function factorial(i, a = 1) {
  if (i < 2) {
    return a;
  }
  return factorial(i - 1, a * i);
};
var trailingZeroes = function (n) {
  let ans = factorial(n)
  if (n[n.length-1]===0) {
    return 1
  } else {
    return 0
  }
};

不过在输入超过1808548329之后，就会暴栈。。

image-20190810210623753

观察法

作者：chen-chen-6

链接：https://leetcode-cn.com/problems/two-sum/solution/tou-ji-qu-qiao-de-suan-fa-ti-by-chen-chen-6/

如果要让最后一位是0，那么这必须是2(及其倍数)和5(及其倍数)相乘得出的。换言之是在找这个阶乘数中能匹配多少对2和5。

而又因为一个数字进行拆分后 2 的个数肯定是大于 5 的个数的，所以能匹配多少对取决于 5 的个数。

换言之问题就变成了，这个数字能拆出多少个5。

作者：icemelon

链接：https://leetcode-cn.com/problems/two-sum/solution/chan-sheng-ling-de-tiao-jian-by-icemelon/

var trailingZeroes = function (n) {
  let ans = 0
  while (n >= 5) {
    n = Math.floor(n / 5)
    ans += n
  }
  return ans
};

Runtime: 56 ms, faster than 86.96% of JavaScript online submissions for Factorial Trailing Zeroes.

Memory Usage: 34.3 MB, less than 25.00% of JavaScript online submissions for Factorial Trailing Zeroes.

好吧其实还是看不太懂，但是似乎可以实现。。

func trailingZeroes(n int) int {
    var ans int
    for n >= 5 {
        n /= 5
        ans += n
    }
    return ans
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forFactorial Trailing Zeroes.

Memory Usage: 2 MB, less than 66.67% of Go online submissions forFactorial Trailing Zeroes.

递归也可以

var trailingZeroes = function (n) {
  return n === 0 ? 0 : (Math.floor(n / 5) + trailingZeroes(Math.floor(n / 5)))
};

Runtime: 60 ms, faster than 72.73% of JavaScript online submissions for Factorial Trailing Zeroes.

Memory Usage: 34.1 MB, less than 25.00% of JavaScript online submissions for Factorial Trailing Zeroes.

func trailingZeroes(n int) int {
    if n == 0 {
        return 0
    } else {
        return n/5 + trailingZeroes(n/5)
    }
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forFactorial Trailing Zeroes.

Memory Usage: 2 MB, less than 66.67% of Go online submissions forFactorial Trailing Zeroes.

计算go的代码是不是坏掉了呀。。