factorial problem-- no of zeroes

[catchmrbharath]

I was trying to find the number of zeroes in a factorial of a number. The time limit was 2 sec. Max number of test cases being 100000

my code is as follows

#include<iostream>
#include<cstdio>
int five(int number);
 int two(int number);
using namespace std;
main()
{

  int num;
  int t,i;
  int no_five=0,no_two=0;
  scanf("%d",&t);
  for(i=0;i<t;i++)
    {
      scanf("%d",&num);
      for(int j=1;j<=num;j++)
	{
	  no_five+=five(j);
	  no_two+=two(j);
	}
      if(no_five>no_two)
	printf("%d\n",no_two);

      else
	printf("%d\n",no_five);

      no_five=0;
      no_two=0;

    }
}



int five(int num)
{
  int i=0;
  while(num%5==0)
    {
      i++;
      num/=5;
    }
  return i;
}


int two(int num)
{
  int i=0;
  while(num%2==0)
    {
      i++;
      num/=2;
    }
  return i;
}

Please tell me how to optimize my approach

[Salem]

Well while you're waiting, consider reading the forum rules on how to post code, then edit your code for readability.

[siddhant3s]

The first optimization advice is "Don't optimize anything".
Second advice: Stick to one language C or C++. You are using lot of scanfs and printfs.
It goes without say that post your code it code tags:

[code=cpp] //your code

[/code]

[csurfer]

Its better not to paste the questions given in other portals for you to solve here for us to solve. But since you have tried to code this is my view...

>You are trying to find out factors of 2 and 5 for every number within a limit "num" for this you are calling two functions five() and two() for every num starting from 1 and ending at num.
>Instead try finding the factors for factorial itself,in this way you will call those functions only once for every factorial and multiplication would take minimum time when compared to function call for every number.

[mvmalderen]

main() , this is not C++ !
In C++ it would look like: int main() :)

[mvmalderen]

Not that difficult:
(If you understand how logarithms work, then this is a piece of cake :P)

The standard trick is to use the logaritm in base 10.

Let x = lg(8600!). Since lg(xy)=lg(x)+lg(y) you have

x = sum(lg(k),k=1..86000)

Define floor(x) as the integer part of x. Then

86000! = 10^(x-floor(x))*10^floor(x).

You can evaluate x to the degree of accuracy you want, for example,
using Maple I got:

86000! = 7.91222558*10^372239

The computation time was close to 0.

(Source: http://answers.google.com/answers/threadview/id/33709.html)

:P

Edit:: Remark, the above explanation is no real C code, but you can quickly adapt it...

[mvmalderen]

Or...take a look at this :)
( It's a better way than the way described in my previous post, sorry :$)

[siddhant3s]

Ya there solution is pretty trivial. Kummer Theorem is the right way.
The answer would the exact power of the five in the given number.
AFAIR: the exact power was calculated as
[tex]\sum_{n=1}^{\infty}floor(\frac{N}{p^n})[/tex]
where N is the number and p =5 in this case. This sum is actually finite since all the terms to the right of the(and including) term where N< p^n will be zero.

[catchmrbharath]

Thanks it worked

[Sky Diploma]

I guess the solution can be calculated in the following way as well.

int x=0;
int number=10000;
while(number!=0)
{
 number=number/5;
 x+=number;
}