9
\$\begingroup\$

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;
    }
\$\endgroup\$
  • \$\begingroup\$ What do you mean with "I am basically trying to find the number of 5's and 2's, to obtain 10"? \$\endgroup\$ – Ben Steffan Oct 18 '17 at 16:25
  • \$\begingroup\$ @BenSteffan: He's counting the how often the factors of the factorial are divisible by 5 or 2. The smaller of those counts is equal to how often the factorial will be divisible by 10. \$\endgroup\$ – hoffmale Oct 18 '17 at 16:29
  • \$\begingroup\$ @Ben, I think what's meant is that the number of 5's in the prime factorization determines how many times you can divide by 10. (Obviously, there are at least as many 2's as 5's, so that can't be the limiting factor). \$\endgroup\$ – Toby Speight Oct 18 '17 at 16:29
  • \$\begingroup\$ Not the main problem with your approach - but modulo operations are computationally quite expensive... \$\endgroup\$ – Floris Oct 18 '17 at 18:02
  • \$\begingroup\$ @Floris : Could you suggest an alternate method without using modulo? \$\endgroup\$ – Shardul Vikram Singh Oct 18 '17 at 19:42
8
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ It turns out that I actually answered that code-golf challenge four times (in different languages - including C). Any of them may be instructive, but they are written for golfing rather than readability - but that might give you some entertainment and education as you unpick them! \$\endgroup\$ – Toby Speight Oct 19 '17 at 9:51
7
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ After a night's sleep (the above was at 2am), I think you only need to count the times 5^N (5 to the power of N) divides into T, with a loop on N++, N>0. Stop the loop when 5^N > T. Why does this work - Since there are so many more 2 factors than 5 factors, any 5^N essentially becomes a number with N zeroes at the end (5x2=10, 25x4=100, 125x8=1000, etc.). Just up to 100!, there are 50 2-factors, but only 20 5-factors, giving us this surplus of 2s that make this work. \$\endgroup\$ – Jim Oct 19 '17 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.