【leetcode系列】172. 阶乘后的零

题目描述

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

示例 1:

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

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。


来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/factorial-trailing-zeroes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

我们需要求解这n个数字相乘的结果末尾有多少个0,由于题目要求log的复杂度,因此暴力求解是不行的。

通过观察,我们发现如果想要结果末尾是0,必须是分解质因数之后,2 和 5 相乘才行,同时因数分解之后发现5的个数远小于2, 因此我们只需要求解这n数字分解质因数之后一共有多少个5即可.

如图如果n为30,那么结果应该是图中红色5的个数,即7。

我们的结果并不是直接f(n) = n / 5, 比如n为30, 25中是有两个5的。 类似,n为150,会有7个这样的数字,通过观察我们发现规律 f(n)=n/5+n/5^2+n/5^3+n/5^4+n/5^5+..

如果可以发现上面的规律,用递归还是循环实现这个算式就看你的了。

关键点解析

  • 数论

代码

/*
 * @lc app=leetcode id=172 lang=javascript
 *
 * [172] Factorial Trailing Zeroes
 */
/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
  // tag: 数论

  // if (n === 0) return n;

  // 递归:f(n) = n / 5 + f(n / 5)
  // return Math.floor(n / 5)  + trailingZeroes(Math.floor(n / 5));
  let count = 0;
  while (n >= 5) {
    count += Math.floor(n / 5);
    n = Math.floor(n / 5);
  }
  return count;
};

原文发布于微信公众号 - 脑洞前端(fe_lucifer)

原文发表时间:2019-08-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券