Last digit of factorial (TLE)

[yabi2943993]

I just made a program to calculate the last digit of the factorial of an int:

#include <iostream>

int main() {
    int casos;
    std::cin>>casos;
    int num;
    int fact=0;
    for(int n=0;n<casos;n++){
        std::cin>>num;
        fact=num;
        while(num>=2){
            fact*=(num-1);
            num--;
        }
        std::cout<<fact%10<<"\n";
    }
	return 0;
}

Is there any way to simplify this problem, so it takes less time to run. Maybe another algorithm? Or maybe can change a loop for another operation?

[lastchance]

The last digit of 0! or 1! is 1.
The last digit of 2! is 2.
The last digit of 3! is 6.
The last digit of 4! is 4.
The last digit of any higher factorial is ... 0.

[yabi2943993]

Thanks lastchance

[dutch]

A little math goes a loooooong way. :)

More generally, for n!, the number of zeroes it ends in is n / 5 + n / 25 + n / 125 + ... (integer division).

int num_zeroes(int n) {
    int z = 0;
    while (n) {
        z += n / 5;
        n /= 5;
    }
    return z;
}

Is there a clever way to determine the highest-order digit?

[lastchance]

dutch wrote:

Is there a clever way to determine the highest-order digit?

Hi dutch,
In the unlikely event this works, it would definitely go down as cheating! "Clever" it isn't!

Don't expect it to work for very big numbers.

#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;

int firstDigitOfFactorial( int N )
{
   stringstream ss;
   ss << tgamma( N + 1.0 );
   return ss.str()[0] - '0';
}

int main()
{
   for ( int i = 1; i <= 50; i++ ) cout << i << "  " << firstDigitOfFactorial( i ) << '\n';
}

[dutch]

"Clever" it isn't!

I guess it's more knowledgeable than clever. :)
I wouldn't have thought of it.
It works up to 170, and then the tgamma function returns inf.

https://en.wikipedia.org/wiki/Gamma_function

[lastchance]

@Dutch, apparently there's a log(gamma) function, too! This goes considerably higher:

#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;

int firstDigitOfFactorial( int N )
{
   stringstream ss;
   double temp = lgamma( N + 1.0 ) / log( 10.0 );
   ss << pow( 10.0, temp - (long long)temp );
   return ss.str()[0] - '0';
}

int main()
{
   for ( int i = 1; i <= 100; i++ ) cout << i << "  " << firstDigitOfFactorial( i ) << '\n';
}

It's correct for 1000000 according to the table here:
https://en.wikipedia.org/wiki/Factorial

[dutch]

@lastchance, That's insane! I'm going to have to read up a little on the gamma function. I'm curious as to how it does that.

[lastchance]

Well, N! is gamma(N+1), but I'm sure you knew that.

lgamma() gives the natural log of gamma, so lgamma()/log(10) will give the base-10 logarithm of gamma.

If I take 10 to the power of this then, in theory, I would get gamma(). However, the numbers would be huge and would overflow. But such numbers could be divided by 10 to any integer power p without changing the first digit; conveniently you could achieve the same by subtracting p from the logarithm before taking 10 to the power. The most convenient p to use, which keeps the resulting numbers very small, is the integer part of log10(gamma()).


I've no idea why they occur, but I'm struck by the length of some of the repeats of that first digit for successive factorials.

[dutch]

I'm struck by the length of some of the repeats of that first digit for successive factorials.

I noticed that, too. Here's an interesting run (reps in last column):

 997216:  3   105
 997321:  2   156
 997477:  1   291
 997768:  9    47
 997815:  8    55
 997870:  7    64
 997934:  6    75
 998009:  5    94
 998103:  4   122
 998225:  3   170
 998395:  2   276
 998671:  1   712
 999383:  9   204
 999587:  8   826
1000413:  9   205
1000618:  1   712
1001330:  2   276
1001606:  3   170

[lastchance]

I guess that it's happening near powers of 10. Then the factorial is effectively being multiplied by something like 1.00abc x 10^n, so multiplying by something like 1 (times a power of 10) doesn't change the first digit.

Might come in useful one day, I suppose.