2
\$\begingroup\$

I am solving a problem on calculation of factorial and the challenge is as follows!

You are asked to calculate factorials of some small positive integers.

Input

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines,
each containing a single integer n, 1<=n<=100.

Output 

For each integer n given at input, display a line with the value of n!

My Code is giving me the correct solution but Time limit is exceeded which is 2 seconds:

The code is as follows:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
void factorial(int N)
{
    printf("\n\n");
    int q,i,j,t,d,z;
    float p=0.0;
    for(i=2;i<=N;i++)
    p=p+log10(i);
    d=(int)p+1;//No of terms in the factorial
    int *b;
    //initialization of an array
    b=(int *)malloc(d*sizeof(int));
    b[0]=1;
    for(i=1;i<d;i++)
    b[i]=0;
    //calculation of factorial
    p=0.0;
    for(j=2;j<=N;j++)
    {
        q=0;
        p=p+log10(j);
        z=(int)p+1;
        for(i=0;i<N;i++)
        {
           t=(b[i]*j)+q;
           q=t/10;
           b[i]=t%10;   
        }
    }
    for(i=d-1;i>=0;i--)
    printf("%d",b[i]);

}
int main()
{
    int n,i,j;
    scanf("%d",&n);
    int *b;
    b=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
    }
    for(i=0;i<n;i++)
    factorial(b[i]);
    return 0;
}

How can i make my program more efficient and produce the output in the given time limit? This challenge is from HackerEarth

\$\endgroup\$
3
\$\begingroup\$

The best solution is only to compute the factorials you need and only compute them once.

  1. Read all the user input find the maximum value.
  2. Generate the factorials for all values upto the max
    Note: Saving them as you go:
  3. Print the factorial values by looking up the result you generated in 2.

So lets look at the code:

I would not bother dynamically allocating the data storage.

    b=(int *)malloc(n*sizeof(int));

The question specifically limits the maximum value of n to 100.

    int b[101]; // should be suffecient

When reading values this should work (if you assume that the input is good).

        scanf("%d",&b[i]);

But the question states that the input is one value per line. Personally I would validate that there is one value per line.

Here you are calculating the factorial multiple times:

    for(i=0;i<n;i++)
       factorial(b[i]);  // Factorial is O(n)
                         // Thus this loop is O(n^2)

Technically you only need to call factorial once. If you calculate factorial for 'n' you need to calculate the factorial for 'n-1' (its how it is defined). If you store the numbers then you only need to look up the values to print it once they have been calculated.

It seems like you calculate this value each time.

    float p=0.0;
    for(i=2;i<=N;i++)
    p=p+log10(i);

The worst case scenario is that you need to calculate this for a value of 100. You only need to calculate this one for 100. Also you can calculate it off line and now it is a const expression.

This is then a const expression and thus you don't need to calculating it.

    b=(int *)malloc(d*sizeof(int));

But you do need 100 of them so you can store all intermediate values:

You don't need to loop over an array to initialize it:

    for(i=1;i<d;i++)
        b[i]=0;

You can initialize it already zero'd out. For dynamic memory use calloc() for automatic arrays use = {0};

So the above two can be combined into;

    const int d = <pre-calculated value>;
    int b[100][d] = {0};
    b[0][0] = 1;
    b[1][0] = 1;
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

The following comments are somewhat related :

  • Your factorial function should probably be called printFactorial.

  • You should separate the computing logic and the printing logic.

  • You could use/implement a way to handle Big Integers in a clearer way. Here you are handling (if I understand correctly) each digit individually. (To be honest, I haven't even tried to understand how things are supposed to work at the moment because as everything is happening in a single place, it's hard to tell what's intended).

  • You could cache the results (you compute the factorial for all numbers from 1 to 100 once and for all and then you just loop on the input, fetch the corresponding value from your cache and print it).

  • You don't need to store the input values in an array:

You could just do something like :

 int n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
    int b=0;
    scanf("%d",&b);
    factorial(b);
}
return 0;
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.