Number of last "0" digits??

[awkedd]

Hello! I have to create a function that returns the number of "0" digits at the end of the number n! .
for example, zerof(6)=1 , because 6!=720 and there is only one 0 at the end.
The site I submitted it to says it's not fast enough.How can I improve it? Thank you

 iint zerof(int n){
    int z=1, c=0;
for(int i=1;i<=n;i++)
{
    z=z*i;
}
do{
    c++;
    z=z/10;
}
while(z%10==0);

return c;
}

[helios]

How is that not fast enough? The loop between lines 3 and 6 will overflow z really quickly anyway.

[awkedd]

@helios I have no idea!

[AbstractionAnon]

I have no comment on the speed of your code, but from what I see your do/while is going to give you the wrong answer under certain conditions.

At line 7, consider if z does not end in 0. You're going to execute the loop at least once causing c to be incremented to 1.

[helios]

Counting has got to be faster than division

Converting a number to a string implies performing division. std::stringstream allocates memory as well.

I have no idea!

Why are you saying it's not fast enough, then?

[awkedd]

@helios Because i get the error "time limit exceeded"

[lastchance]

Sorry @Helios - I deleted a post (because I was wrong!!).

As @Helios pointed out, actually computing the factorial is going to overflow even a long int very quickly, so this isn't really practicable.

You may (and no, I haven't tried it!) be able to do it by a cumulative count, which saves multiplying and dividing. As you climb from 1 to n you will get:
- one or more extra zeroes for every multiple of 10 (one from 10, 20, ...; two from 100, 200, ... etc.)
- one extra zero every time you pass an odd multiple of 5 (because you must also have passed a number ending in 2).

The second source of these is just (n+5) (integer divided by) (10); that's OK and gives f(6)=1.
The first is a bit more difficult ...

[awkedd]

Apparently, this is the 100-point code:
<code>
Int zerof(int n)
{
int i, x, fm5, ct = 0;
for(i = 1; i <= n; i ++)
{
x = i;
fm5 = 0;
while(x % 5 == 0)
{
fm5 ++;
x = x / 5;
}
ct = ct + fm5;
}
return ct;
}
</code>

[lastchance]

Hmm, I can't count properly.

Unique prime factorisation gives extra zero for every extra factor of 2*5.
Many more factors of 2 than 5, so, effectively, an extra zero for every extra factor 5.
So, add one extra zero for multiples of 5, or two extra zeroes for multiples of 5*5, etc.
This can be added up as
n/5 + n/(5*5) + n/(5*5*5) + ... where integer division is assumed.

Here's my take (which gives the same answers as the "official" one, up to at least 100000).

#include <iostream>
using namespace std;


int zerof( int n )
{
   int multipleOfPower = n / 5;
   int result = 0;
   while( multipleOfPower > 0 )
   {
      result += multipleOfPower;
      multipleOfPower /= 5;
   }
   return result;
}



int main()
{
   int n;
   cout << "Input n: ";   cin >> n;
   cout << "zerof(n) = " << zerof( n ) << endl;
}

Nice post though!