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啦~!

发表评论