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 …