online advertising

Monday, March 30, 2015

LeetCode OJ - Factorial Trailing Zeroes

Problem:

Please find the problem here.

Solution:

In order to have a trailing zero, there must be a factor of 10, there are plenty of 2 there, so the limiting factor is the number of 5 as a factor.

For all multiples of 5, we count 1.
For all multiples of 25, we should count two, but note that in the above step we already counted 1 for it, so just count 1.
For all multiples of 125, we should count three, but note that in the two above steps we already counted 2 for it, so again, just count 1.

Now we get the pattern, just count 1 for all multiples of all powers of 5, that's is.

Be careful with overflow, that's it.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/factorial-trailing-zeroes/

#include "LEET_FACTORIAL_TRAILING_ZEROES.h"
#include <map>
#include <iostream>
#include <vector>

using namespace std;

namespace _LEET_FACTORIAL_TRAILING_ZEROES
{
    class Solution
    {
    public:
        int trailingZeroes(int n)
        {
            int numZeros = 0;
            long long p = 5;
            while (p <= n)
            {
                numZeros += n / p;
                p *= 5;
            }
            return numZeros;
        }
    };
};

using namespace _LEET_FACTORIAL_TRAILING_ZEROES;

int LEET_FACTORIAL_TRAILING_ZEROES()
{
    Solution solution;
    cout << solution.trailingZeroes(2147483647) << endl;
    return 0;
}

No comments :

Post a Comment