Factorial Trailing Zeroes (Divide-and-Conquer)

5169 ワード

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があるか、125625があるかを見ることに相当します.
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