算法小练——尾部的零

---

title: 算法小练——尾部的零 categories:

Algorithms tags:esay abbrlink: 1163077827 date: 2019-11-02 13:27:51

---

---

描述

设计一个算法，计算出n阶乘中尾部零的个数

您在真实的面试中是否遇到过这个题？ 是

题目纠错

样例

样例 1: 输入: 11 输出: 2 样例解释: 11! = 39916800, 结尾的0有2个。 样例 2: 输入: 5 输出: 1 样例解释: 5! = 120， 结尾的0有1个。

挑战

O(logN)的时间复杂度

代码

public class Solution { /* * @param n: An integer * @return: An integer, denote the number of trailing zeros in n! */ public long trailingZeros(long n) { // write your code here, try to do it without arithmetic operators. long count = 0; long temp=n/5; while (temp!=0) { count+=temp; temp/=5; } return count; } }

笔记

这道题的实质，就是求5的个数，有多少个5就有多少个0. 那怎么怎么求5的个数呢? 最开始想到的就是，遍历每个数，并对每个数取模%，直到模后的值小于5结束 但是结果发现超时了

不符合题目要求的复杂度

于是观察发现 1 -10 有 5 10 2个5值 1-20 有 5 10 15 20 4个5的值 1-30 有5 10 15 20 25 30 表面看来是 6个5的值，但是 25 是 55 ，所以25则分成 2个，最后是7个 规律 ：10 = 25 20 = 45 30 = 65 +1 40 = 85+1 那么 1-50 呢 50 = 105+2 所以就是得 几个5 +几个55+几个 55*5 …