Page 1 of 1

1185 - Big Number

Posted: Fri Jul 18, 2014 10:31 am
by rafid059
I am getting WA! Can anyone help me, please??

Code: Select all

Accepted!   :D
}

Re: Problem 1185 --- Big NUmber

Posted: Fri Jul 18, 2014 12:06 pm
by 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. 8)

Re: Problem 1185 --- Big NUmber

Posted: Mon Jul 21, 2014 11:49 pm
by rafid059
lighted, thanks again! :D

1185 - Big Number

Posted: Wed Sep 17, 2014 10:36 pm
by 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;
}

Re: 1185 - Big Number

Posted: Thu Sep 18, 2014 3:44 pm
by 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). :)

Re: 1185 - Big Number

Posted: Fri Sep 19, 2014 1:57 pm
by 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. :)

Re: 1185 - Big Number

Posted: Mon Mar 14, 2016 6:15 pm
by 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.