Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

 

这个题目貌似十分清晰，求n的阶乘，末尾的0个数

末尾为0的个数，也就是2 * 5的个数，但是前提是所有的数都分解成了质数，而显然分解之后2肯定比5多，所以最终只需要得到所有相乘的数字里，能够分解出多少个5

C直接来两轮，提交

int trailingZeroes(int n) {
    int i, tmp;
    int j = 0;
    for (i = 1; i <= n; i++){
        tmp = i;
        while (tmp % 5 == 0){
            ++j;
            tmp = tmp / 5;
        }
    }
    return j;
}

给出的反馈，一开始还没看明白

Submission Result: Time Limit Exceeded

Last executed input:	1808548329

貌似意思是input了下面那个大数字之后，程序运行时间超过了设定的阀值，提交没通过，不过这代码两轮的确看上去比较难看，要减少下复杂度

突然想到，既然是分解为5的个数，那肯定都是5的倍数，那么相差为5，这样减少遍历的数字

第二次提交

int trailingZeroes(int n) {
    int i, tmp;
    int j = 0;
    for (i = 5; i <= n; i += 5){
        tmp = i;
        while (tmp % 5 == 0){
            ++j;
            tmp = tmp / 5;
        }
    }
    return j;
}

但是纳闷的是，依旧是这种提示

Submission Result: Time Limit Exceeded 

Last executed input:	1808548329

这么看来，铁定要那两个循环开刀

继续看了看，突然发现自己傻了，既然 i 都是5的倍数了，while里还取模干嘛，神经~！先除了再说

第三次提交

int trailingZeroes(int n) {
    int i, tmp;
    int j = 0;
    for (i = 5; i <= n; i += 5){
        tmp = i / 5;
        ++j;
        while (tmp % 5 == 0){
            ++j;
            tmp = tmp / 5;
        }
    }
    return j;
}

结果依旧，我也是醉了~！不过这也正是Leetcode吸引我的地方，能力不够就得补~！

Submission Result: Time Limit Exceeded

Last executed input:	1808548329

冷静地缕一缕，比如n = 100，遍历5，10，15，20，25，30，35，40，45，50，55，60，65，70，75，80，85，90，95，100；首先除以5之后，是100 / 5 = 20个5，遍历所有商1~20；还有5和10，15，20继续可以分解出5，也就是20 / 5 = 4个5；继续遍历商1，2，3，4……

这么看来，实际上只需要不停遍历除以5的商即可，根本不需要考虑找出5的倍数的数字，新潮澎湃

第四次提交

int trailingZeroes(int n) {
    int j = 0;
    while (n){
        j += n / 5;
        n = n / 5;
    }
    return j;
}

应该没问题，突然感觉很有成就感

502 / 502 test cases passed.
Status: Accepted
Runtime: 3 ms

终于OK啦~！