Calculating the number of zeroes at the end of a factorial

Question

The code seems to work, but, I always get the "Time Limit Exceeded" error (the time limit defined is 6 seconds). I even tried reducing the number of iterations but am still running short on time. I am basically trying to find the number of 5's and 2's, to obtain 10.

#include <iostream>

int number_counter(long int x, int base)
{
long int val = x;
unsigned int counter = 0;
for(long int i = x; i >= 1;(!(i%base)?(i=i-base):i--))
{
    val =i;
    while((val % base) == 0)
    {
        counter++;
        val = val/base;
    }
}
return counter;

} 

int Zfact(long int num)
{
    unsigned int fives, twos;
    fives = number_counter(num, 5);
    twos = number_counter(num, 2);
    return (fives>twos) ? twos : fives;
}
int main() {
    int T;                                  //T = Number of test cases.
    cin>>T;
    unsigned long int n;
    for(int i=0;i < T;i++)
    {
        cin>>n;
        int zeroes = Zfact(n);
        cout<<zeroes<<endl;
    }

    return 0;
    }

Answer 1

This challenge looks familiar - I think I answered a similar challenge on our sister site, Programming Puzzles and Code Golf. Those answers may not be as readable, though.

There's a couple of pieces of good news:

1. You don't need to count 2's in the prime factorization. There will always be more 2's than 5's, so you can never have an unpaired 5.
2. You don't need to iterate over every number up to num if you see that we're just computing n/5 + n/25 + n/125 + ... (integer division). If we define f(n) = n/5 + f(n/5) and f(0) = 0, we have a much faster version. That can be implemented recursively, or fairly easily converted to iterative form.

Answer 2

I'll leave the pleasure of actually solving this problem to you, but here are some questions that may help:

1. Are there ever going to be more 5s than 2s?
2. What's a shorter expression to express the number of 5s in a number?

Format your code better

The indentation of your code is a little strange. Better looking code is easier to read and maintain.

Don't make additional copies of parameter

The parameters in your code are passed by value. This means that they're copies already so you don't need to make another copy. Use the passed variable directly instead.

Answer 3

Since 5 times any even number gives 1 extra '0', do you really need to worry about iterating through to count the 5's? Can't you just divide T / 5 as an integer to get the 5_count, then divide that by 2 to filter out the 10s (which are counted below).

The real trick is to iterate through dividing T by 10, 100, 1000, etc., and adding those directly to your count.

This should be pretty efficient. As T grows by an order of magnitude, you just have 1 more "divide T by 10^x" calculation.

An example should help:

For 91!

There are 9 10s (10,20,30,40,50,60,70,80,90)

There are 9 more 5s (5,15,..,85)

So, 91! ends with 18 zeroes.

Note that I did not actually calculate 91! out, so feel free to tell me if I'm wrong.

---

OK, Wolfram Alpha tells me I'm off by 3 '0's - it should be 21.

So, I missed that you have to handle T/25 or T/125, etc. with each order of magnitude iteration. By included T/25, you get the 3 extra '0's for 25, 50, & 75.