Count how many trailing zeroes n! has. The problem essentially reduces to counting the number of factor 5 in the prime factorization (since there are always more 2s than 5s). A naive approach of checking every number modulo 5 would time out; instead, you only need to compute the relationship between powers of 5 and n.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int trailingZeroes(int n) {
vector<int> five(14);
for (int i = 1; i <= 13; i++) {
five[i] = ((int)pow(5.0, i));
}
int before = 0;
int count = 0;
for (int i = 13; i >= 1; i--) {
if (five[i] <= n) {
count += (n / five[i] - before) * i;
before = (n / five[i]);
}
}
return count;
}
};
|