2. Trailing Zeros

Description

Write an algorithm which computes the number of trailing zeros in n factorial.

Example

11! = 39916800, so the out should be 2

Challenge

O(log N) time

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 否则超出范围        long cou = 0;        long temp = n / 5;                while(temp != 0){            cou += temp;            temp = temp / 5;        }        return cou;                 }}

/笔记/weix612 的笔记返回weix612最后更新于 15 小时前假如你把1 × 2 ×３× 4 ×……×N中每一个因数分解质因数，结果就像： 1 × 2 × 3 × (2 × 2) × 5 × (2 × 3) × 7 × (2 × 2 ×2) ×…… 10进制数结尾的每一个0都表示有一个因数10存在——任何进制都一样，对于一个M进制的数，让结尾多一个0就等价于乘以M。10可以分解为2 × 5——因此只有质数2和5相乘能产生0，别的任何两个质数相乘都不能产生0，而且2，5相乘只产生一个0。 所以，分解后的整个因数式中有多少对(2, 5)，结果中就有多少个0，而分解的结果中，2的个数显然是多于5的，因此，有多少个5，就有多少个(2, 5)对。 所以，讨论1000的阶乘结尾有几个0的问题，就被转换成了1到1000所有这些数的质因数分解式有多少个5的问题。假设有序列1、2、3、4、5、6、7、8、9、10、11、…分析上面的数列可知，每5个数中会出现一个可以产生结果中0的数字。把这些数字抽取出来是：…、5、…、10、…、15、…、20、…、25、…这些数字其实是都能满足5*k的数字，是5的倍数。统计一下他们的数量：n1=N/5。比如如果是101，则101之前应该是5,10,15,20,…,95,100共101/5=20个数字满足要求。整除操作满足上面的数量统计要求。将1中的这些数字化成5*(1、2、3、4、5、…)的形式，内部的1、2、3、4、5、…又满足上面的分析：每5个数字有一个是5的倍数。抽取为：…、25、…、50、…、75、…、100、…、125、…而这些数字都是25的倍数（5的2次幂的倍数），自然也都满足5k的要求。这些数字是25、50、75、100、125、…=5(5、10、15、20、25、…)=55(1、2、3、4、5、…)，内部的1、2、3、4、5、…又满足上面的分析，因此后续的操作重复上述步骤即可。统计一下第二次中满足条件的数字数量：n2=N/5/5，101/25=(101/5)/5=4。因为25、50、75、100、125、…它们都满足相乘后产生至少两个0，在第一次5k分析中已经统计过一次。对于N=101，是20。因此此处的55*k只要统计一次4即可，不需要根据25是5的二次幂统计两次。后面的125,250,…等乘积为1000的可以为结果贡献3个0的数字，只要在55k的基础上再统计一次n3=((N/5)/5)/5即可。核心点：尾部的零有5的个数决定，单5（因式分解后有1个5）与某偶数相乘有单0，多5（因式分解后有多个5）与某偶数相乘有多个0。

描述设计一个算法，计算出n阶乘中尾部零的个数您在真实的面试中是否遇到过这个题？  样例11! = 39916800，因此应该返回 2挑战O(logN)的时间复杂度