Factorial Trailing Zeroes
A trailing zero is made of factor 2 and factor 5
n! = 2 ^ m * 5 ^ n * (other factors)
the count of trailing zero is min(m, n)
.
because a 2
and a 5
generates a zero.
the work is just counting 2 and 5 ...
Source code Read on Github
1 public class Solution {
2 public int trailingZeroes(int n) {
3
4 int count = 0;
5
6 int c2 = 0; // count of 2
7 int c5 = 0; // count of 5
8
9 for (int i = 1; i <= n; i++){
10 int m = i;
11
12 while(m % 5 == 0){
13 m /= 5;
14 c5++;
15 }
16
17 while(m % 2 == 0){
18 m /= 2;
19 c2++;
20 }
21
22 int c = Math.min(c2, c5);
23
24 count += c;
25 c2 -= c;
26 c5 -= c;
27
28 }
29
30 return count;
31
32 }
33 }