1185 - Big Number

All about problems in Volume 11. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

1185 - Big Number

Post by rafid059 » Fri Jul 18, 2014 10:31 am

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

Post by lighted » 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. 8)
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

Post by rafid059 » Mon Jul 21, 2014 11:49 pm

lighted, thanks again! :D

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

1185 - Big Number

Post by nahin.ruet12 » 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;
}

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

Re: 1185 - Big Number

Post by lighted » Thu Sep 18, 2014 3:44 pm

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

Post by lighted » 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. :)
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

Post by Bryton » 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.

Post Reply

Return to “Volume 11 (1100-1199)”