Page 1 of 1

### 1185 - Big Number

Posted: Fri Jul 18, 2014 10:31 am
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
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.

### Re: Problem 1185 --- Big NUmber

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

### 1185 - Big Number

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

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
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
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.