How to reduce this piece of code in order to avoid TLE

Question

The program is to find the number of digits in a factorial of a number

#include <stdio.h>
#include <math.h>
int main()
{
int n = 0 , i , count = 0 , dig ;
double sum = 0, fact;
scanf("%d" , &n );
for(i=1;i<=n;i++)
{
 sum = sum + log(i);
}
fact = (exp(sum));
while(fact!=0)
{
 dig = ((int)fact%10);
 count++;
 fact = floor(fact/10);
}
printf("%d\n",count);
return 0; 
}

Feel free to comment on making improvements on this code since I don't have a broad experience in Coding yet.

Answer 1

Assuming you don't want to use any mathematical calculation but want to "brute force" your way through - this would how I would shorten your run time (and mostly clean up you code).

#include <stdio.h>
#include <math.h>
int main()
{
    int n, fact = 1;
    scanf("%d" , &n );
    for (int i = 1; i < n; i++)
        fact *= i;
    
    int sum = 0;
    while (fact != 0)
    {
        fact /= 10;
        sum++
    }

    printf("%d\n",count);
    return 0; 
}

Hopefully this answers your question, good luck!

Answer 2

The reason your code is taking so long is that once n reaches about 180, the value of fact becomes too large to hold in a double-precision floating point variable. When you execute this line:

    fact = (exp(sum));

you're basically setting fact to a value of infinity. As a result, the following while() loop never terminates.

There's also not much point calculating logarithms in your code. It will only slow things down. Just calculate the factorial in a double variable and reset it whenever it gets too large. Like this, for example:

int factorial_digit_count(int n) {
    int i, nd=1;
    double f = 1.0;
    for (i=2; i<=n; i++) {
        f *= i;
        if (f > 1.0E+100) {
            f /= 1.0E+100;
            nd += 100;
        }
    }
    while (f > 1.0E+10) {
        f /= 1.0E+10;
        nd += 10;
    }
    while (f >= 10.0) {
        f /= 10.0;
        nd++;
    }
    return nd;
}

Answer 3

There is a simple relationship between the base b logarithm of a number and the base b representation of that number:

len(repr(x, b)) = 1 + floor(log(x, b))

In particular, in base 10, the number of digits in x is 1 + floor(log10(x)). (To see why that's the case, look at the result of that formula for powers of 10.)

Now, the logarithm of a×b is the sum of the logarithms of a and b. So the logarithm of n! is simply the sum of the logarithms of the integers from 1 to n. If we do that computation in base 10, then we can easily extract the length of the decimal expansion of n!.

In other words, if you sum the log10 of each value instead of the log, then you can get rid of:

fact = (exp(sum));

and

while(fact!=0)
{
 dig = ((int)fact%10);
 count++;
 fact = floor(fact/10);
}

and just output 1 + floor(sum).

In theory, that could suffer from a round-off error. However, you'd need to do an awful lot of logarithms in order for the error term to propagate enough to create an error in the computation. (Not to say it can't happen. But if it happens, n is a very big number indeed.)