chipette - 1 year ago 88
Java Question

# Trailing Zeroes of a Factorial

I'm trying to solve this coding question:
Given an integer n, return the number of trailing zeroes in n!

Below is my code (codec this up using the wiki link)

``````    public int trailingZeroes(int n) {
int count = 0, i = 5;
while(i<=n){
count+= n/i;
i*=5;
}
return count;
}
``````

This runs for all test cases except when n = Integer.MAX_VALUE upon which I get a TLE. How can I fix this code to make it cover that test case. I have read about five articles on the net and everything seems to agree with my approach.

Much thanks.

So, I followed the long/BigInteger approach (thanks y'all):

``````    public int trailingZeroes(int n) {
long count = 0;
for(long i= 5; n/i >= 1; i= i*5){
count+= n/i;
}
return (int)count;
}
``````

Your problem is that once `i` gets large enough (more than `Integer.MAX_INT / 5`) then the line `i*=5;` causes `i` to overflow to the "wrong" value. The value in question is 5 to the 14th power, which is `6103515625`, but which overflows to 1808548329.
The result of this is that the loop just keeps executing forever. `i` will never become a value that's not `<= Integer.MAX_INT`, because there's just no such `int`.
To avoid this, you need `i` to be a larger data type than an `int`. If you change `i` and `count` in your original code to `long`, this will work fine. Of course, `BigInteger` would also work.