chipette chipette - 6 months ago 15
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;
}

Answer

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.