n阶乘中尾部零的个数
in 算法 with 2 comments

n阶乘中尾部零的个数

in 算法 with 2 comments

描述

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

样例

11! = 39916800,因此应该返回 2

假如你把1 × 2 ×3× 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次幂的倍数),自然也都满足5*k的要求。
这些数字是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。

程序

public class Solution {
    public long trailingZeros(long n) {
        long i=0;
        while(n>0){
            i+=n/5;
            n/=5;
        }
        return i;
    }
}

原文链接

Responses
  1. long long trailingZeros(long long n) { // write your code here, try to do it without arithmetic operators. long long res = 0; while (n) { res += n/5; n /= 5; } return res; }

    Reply
  2. 思路
    由于n的阶乘是一个非常大非常大的数,所以先把n的阶乘计算出来肯定是不现实的。发现计算末尾0的个数就是计算能整除几个10,又因为10=2x5,且显然阶乘因子中2的出现频率是肯定比5要高的多的,所以就是所如果能整除5,那么他就一定能整除10。比如n=29,那么发现它的阶乘因子里是5的倍数的有5,10,15,20,25有5个。由于要考虑类似25这样的有多个5的因子,所以把n/5,得n=5,这里5的倍数的因子只有一个5,所以一共有6个5的倍数因子,即末尾有6个0。

    Reply