## Monday, March 30, 2015

### LeetCode OJ - Factorial Trailing Zeroes

Problem:

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;
}