# My Very Simple Java Solution with Clear Explanation

• With the observation that trailing zeroes are originated from 2x5s. We only need to count number of 5 factors in the product 123*...*n.
The number of 5 factors of 1x...x5 is 1
The number of 5 factors of 1x...x25 is 1 x 5 + 1= 6 (because 25 has one more 5 than 5)
The number of 5 factors of 1x...x125 is 6 x 5 + 1 = 31 (because 125 has one ore factor than 25)
.....
So we can calculate the number of 5 factors of 5i
We can convert number n in to base 5. (d1d2...dk)5. The result just = dk * 1 + dk-1 * 6 + dk-2 * 31 + ....

Below is the code implementation. The time complexity is O(logn) and space complexity is O(1).

public int trailingZeroes(int n) {
/*5, 25, 125, trailing zeroes number conforms the relation f(25) = f(5) * 5 + 1
f(125) = f(25) * 5 + 1, .... etc
then convert number n in base 5. The result is the summation of all digit times the corresponding count of that digit.
*/

int res = 0;
int count = 0;
while(n > 0) {
res += (n % 5) * count;
count = count * 5 + 1;
n = n / 5;
}
return res;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.