## 1185 - Big Number

Moderator: Board moderators

rafid059
New poster
Posts: 13
Joined: Thu Feb 27, 2014 6:35 pm

### 1185 - Big Number

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

Code: Select all

``````Accepted!   :D
}``````
Last edited by rafid059 on Mon Jul 21, 2014 11:48 pm, edited 1 time in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

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

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

rafid059
New poster
Posts: 13
Joined: Thu Feb 27, 2014 6:35 pm

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

lighted, thanks again!

nahin.ruet12
New poster
Posts: 5
Joined: Fri Aug 02, 2013 1:26 pm

### 1185 - Big Number

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 1185 - Big Number

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).
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 1185 - Big Number

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Bryton
New poster
Posts: 3
Joined: Mon Mar 14, 2016 6:12 pm

### Re: 1185 - Big Number

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.