Codechef practice question help needed - find trailing zeros in a factorial

Question

I have been working on this for 24 hours now, trying to optimize it. The question is how to find the number of trailing zeroes in factorial of a number in range of 10000000 and 10 million test cases in about 8 secs.

The code is as follows:

#include<iostream>

using namespace std;

int count5(int a){
    int b=0;
    for(int i=a;i>0;i=i/5){
        if(i%15625==0){
            b=b+6;
            i=i/15625;
        }
        if(i%3125==0){
            b=b+5;
            i=i/3125;
        }
        if(i%625==0){
            b=b+4;
            i=i/625;
        }
        if(i%125==0){
            b=b+3;
            i=i/125;
        }
        if(i%25==0){
            b=b+2;
            i=i/25;
        }
        if(i%5==0){
            b++;
        }
        else
            break;

    }
    return b;
}
int main(){
    int l;
    int n=0;
    cin>>l; //no of test cases taken as input
    int *T = new int[l];

    for(int i=0;i<l;i++)
        cin>>T[i]; //nos taken as input for the same no of test cases


    for(int i=0;i<l;i++){
        n=0;
        for(int j=5;j<=T[i];j=j+5){
            n+=count5(j); //no of trailing zeroes calculted 
        }
        cout<<n<<endl; //no for each trialing zero printed
    }

    delete []T;


}   

Please help me by suggesting a new approach, or suggesting some modifications to this one.

Answer 1

Use the following theorem:

If p is a prime, then the highest power of p which divides n! (n factorial) is [n/p] + [n/p^2] + [n/p^3] + ... + [n/p^k], where k is the largest power of p <= n, and [x] is the integral part of x.

Reference: http://planetmath.org/encyclopedia/PrimePowerDividingAFactorial.html

Answer 2

The optimal solution runs in O(log N) time, where N is the number you want to find the zeroes for. Use this formula:

Zeroes(N!) = N / 5 + N / 25 + N / 125 + ... + N / 5^k, until a division becomes 0. You can read more on wikipedia.

So for example, in C this would be:

int Zeroes(int N)
{
    int ret = 0;
    while ( N )
    {
        ret += N / 5;
        N /= 5;
    }
    return ret;
}

This will run in 8 secs on a sufficiently fast computer. You can probably speed it up by using lookup tables, although I'm not sure how much memory you have available.

Here's another suggestion: don't store the numbers, you don't need them! Calculate the number of zeroes for each number when you read it.

If this is for an online judge, in my experience online judges exaggerate time limits on problems, so you will have to resort to ugly hacks even if you have the right algorithm. One such ugly hack is to not use functions such as cin and scanf, but instead use fread to read a bunch of data at once in a char array, then parse that data (DON'T use sscanf or stringstreams though) and get the numbers out of it. Ugly, but a lot faster usually.

Answer 3

You clearly already know the correct algorithm. The bottleneck in your code is the use of cin/cout. When dealing with very large input, cin is extremely slow compared to scanf.

scanf is also slower than direct methods of reading input such as fread, but using scanf is sufficient for almost all problems on online judges.

This is detailed in the Codechef FAQ, which is probably worth reading first ;)