Smallest number n, having k trailing zeros in n! (LightOJ – 1138)

Problem Link: LightOJ 1138

We can easily calculate trailing zeros in n!. But, this problem refers to find the smallest n where n! holds exactly k trailing zeros.

If you don’t know how to calculate trailing zeros of n!. Read here – Trailing Zeros.

The max range of k is 10^8. So, 5*10^8! can easily hold this amount of trailing zero ( as the number of total 5 will be= 5*10^8/ 5 + 5*10^8/ (5*5) + 5*10^8/(5*5*5) +…. ). As, the number of trailing zero increases with the increment of n. Now, search for n and check if that contains k trailing zero or not. Factorial of multiple numbers can contain same numbers of trailing zero, in this problem you just have to find the smallest one, which is obviously a multiple of 5. Now, code it and have a green verdict…

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main ()
{
ll tc,idd=0,b,n,temp,r,i,p,q,c,ans;
scanf("%lld",&tc);
while(tc--)
{
scanf("%lld",&n);
printf("Case %lld: ",++idd);
ans=0;
ll lo=1,hi=5000000000,mid;
while(lo<hi)
{
mid=(lo+hi)/2;
ll cnt=0,tmp=mid;
while(tmp/5)
{
cnt+=tmp/5;
tmp/=5;
}
if(cnt==n)
{
ans=mid;
break;
}
if(cnt<n)
lo=mid+1;
else
hi=mid-1;
}
if(ans)
printf("%lld\n",ans-ans%5);
else
printf("impossible\n");
}
return 0;
}
view raw lightoj1138.cpp hosted with ❤ by GitHub

“For every complex problem there is an answer that is clear, simple, and wrong

H. L. Mencken

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

Create your website at WordPress.com
Get started
%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close