首页 > 代码库 > Factorial Trailing Zeroes (divide and conquer)

Factorial Trailing Zeroes (divide and conquer)

QUESTION

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

Note: Your solution should be in logarithmic time complexity.

FIRST TRY

class Solution {public:    int trailingZeroes(int n) {        int divident;        int nOf2 = 0;        int nOf5 = 0;        while(n%2 == 0)        {            nOf2++;            divident = n/2;        }        while(n%5 == 0)        {            nOf5++;            divident = n/5;        }        return min(nOf2,nOf5);    }};

Result: Time Limit Exceeded

Last executed input: 0

SECOND TRY

考虑n=0的情况

class Solution {public:    int trailingZeroes(int n) {        int divident;        int nOf2 = 0;        int nOf5 = 0;        for(int i = 1; i < n; i++)        {            divident = i;            while(divident%2 == 0)            {            nOf2++;            divident /= 2;            }            divident = i;            while(divident%5 == 0)            {            nOf5++;            divident /= 5;            }        }        return min(nOf2,nOf5);    }};

Result:  Time Limit Exceeded

Last executed input:1808548329

THIRD TRY

2肯定比5多

要注意的就是25这种,5和5相乘的结果,所以,还要看n/5里面有多少个5,也就相当于看n里面有多少个25,还有125,625...

class Solution {public:    int trailingZeroes(int n) {        if(n==0) return 0;        int divident=n;        int nOf5 = 0;        while(divident!= 0)        {            divident /= 5;            nOf5+=divident;        }        return nOf5;    }};

Result: Accepted

 

Factorial Trailing Zeroes (divide and conquer)