LightOj 1189 Sum of Factorials




Hints: The highest number n is 10^18 . So highest factorial is 20! . So at first pre calculate factorials from 0 to 20. Then check from 20 to 0 that factorial is smaller than equal of given number or not. if smaller than equal then push the index to a stack and update the rest number and again check. finally, if given number becomes 0 then you have solution else solution not possible.


#include <bits/stdc++.h>
using namespace std;

int main()
{
     long long int fact[25];
     long long int i,j,k,l,m,n,t;
     //freopen("out.txt","w",stdout);
     fact[0]=1;
     for(i=1;i<=20;i++)
     {
         fact[i]=fact[i-1]*i;
         //cout<<fact[i]<<endl;
     }
     scanf("%lld",&t);
     for(i=1;i<=t;i++)
     {
        stack<int>s;
        scanf("%lld",&n);
        for(j=20;j>=0;j--)
        {
            if(fact[j]<=n)
            {
                n=n-fact[j];
                //cout<<j<<endl;
                s.push(j);
            }
        }

         //cout<<n<<endl;
         if(n==0)
         {
             printf("Case %d: ",i);
             while(s.size()!=1)
             {
                 printf("%d!+",s.top());
                 s.pop();
             }
             printf("%d!\n",s.top());
             s.pop();

         }
         else
         {
             printf("Case %d: impossible\n",i);
         }

     }

     return 0;

}

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment