1185 - Big Number

[rafid059]

I am getting WA! Can anyone help me, please??

Code: Select all

Accepted!   :D
}

[lighted]

Change line

Code: Select all

 double result = 0;

It must be

Code: Select all

 double result = 1;

Also change line

Code: Select all

return (int)Math.ceil(result); 

It must be

Code: Select all

return (int)result; 

Don't forget to remove your code after getting accepted.

[rafid059]

lighted, thanks again!

[nahin.ruet12]

My code showed run time error. I could not find any wrong in code that causes run time error. Please help me finding them...

Code: Select all

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;

int factorialSum[100];

int bigMultipication(char num[], int aa, char *multi)
{
    memset(multi,'0',sizeof(multi));

    int len=strlen(num);

    int temp=0;
    int i;
    int sum=0;

    for(i=0; i<len; i++)
    {
        multi[i]=(((num[i]-48)*aa+temp)%10)+48;
        temp=((num[i]-48)*aa+temp)/10;

        sum+=multi[i]-48;
    }

    if(temp>0)
    {
        while(temp!=0)
        {
            multi[i]=(temp%10)+48;
            temp=temp/10;

            sum+=multi[i]-48;
            i++;
        }
    }

    multi[i]='\0';

    return i;
}

int factorial(int times)
{
    char num[2000];
    char multi[2000]={0};

    num[0]='1';
    num[1]='\0';

    int sum;
    for(int i=1; i<=times; i++)
    {
        sum = bigMultipication(num, i, multi);

        strcpy(num, multi);
    }

    return sum;
}

int main()
{
    int inputNumber;
    cin>>inputNumber;

    for(int i=0; i<inputNumber; i++)
    {
        int num;
        cin>>num;
        cout<<factorial(num)<<endl;
    }

    return 0;
}

[lighted]

Post in existing threads. Don't open new threads.

To avoid RE increase array limit to

Code: Select all

char num[200000];
char multi[200000]={0};

You will get TLE. I solved this problem using a little math. For given number N, to know how many digits a number N has, we can take it's logarithm by base 10 - log10(N).

If N equals to multiplication of k numbers - N = p1 * p2 * p3 * .. *pk.
Using property of logarithm, answer will be log10(N) = log10(p1 * p2 * p3 * .. *pk) = log10(p1) + log10(p2) + .. log10(pk).

You can make precalculation for all values of N in O(N).

[lighted]

We must find value of p, where p is the greatest power of 10 so that 10^p >= N.

Take logarithm of both sides by base 10 and get log10(10^p) >= log10(N).

Finally get p >= log10(N), where p is number of digits of N.

[Bryton]

Is there an algorithm faster than O(n) for this problem? I have AC with precalc using c++11, but it is >0.5s while the fastest ones are ~0.010.