Finding Appending zero’s in a factorial of number upto 10^18


Lets find out number of appending zero’s in a factorial of a number upto 10^18.

Algorithm:
1) Input an integer say num.
2) another integer variable temp=num
3) int divby=5
4) temp=temp/divby
5) ans+=temp
6) temp=num

7) divby=divby*5

8) go to step 4) if num/divby > 0
9) print ans

How this algorithm works?

Multiplication of number with multiple of 5  appends zero to the number.

here I’m finding Quotient of a number /5 first

and then 5^2 , 5^3 ……..until number / 5^n is zero.

by adding those all quotient we get the number of appending zero’s.

#include<iostream>
using namespace std;
int main()
{
long long nu,dev,temp,ans;
int n;
cin>>n;
while(n–)
{
cin>>nu;
temp=nu;
ans=0;
dev=5;
while(temp)
{
temp=nu/dev;
ans+=nu/dev;
dev=dev*5;
}
cout<<ans<<“\n”;
}
}

This is also solution of Spoj Factorial problem 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s