Getting TLE verdict in compute factorial

1 
Given a number N, print N!.

Input Format

First line of input contains T - number of test cases. Its followed by T lines, each containing a single number N.

Constraints

1 <= T <= 1000000
0 <= N <= 1000000

For each test case, print N!. Since the result can be very large, print N! % 1e9+7.

So i tried using BigInteger in java . But on doing that it is giving tle verdict.
Another approach which comes in my mind is precalculate all factorials upto 10^6.
But i’m not sure whether it works or not and also i don’t know how to work with BigInteger arrays.

Can anyone help me ? @everule1 @waqar_ahmad224

Help me

2

the link you have provided is broken I guess.
I am getting a 404 Not found Error

1 Like
3

It’s from smartinterview hackerrank contest.I don’t know why its giving 404 error.

4

Is it a live contest problem?

5

well its open for unlimited amount of time

6

If it’s againast the rules.No problem ill delete this post.
I thought as its similar to our dsa contest in codechef we can ask help.

7

then I can explain.

since we have to print result modulo 10^9+7 , you don’t need bigInteger.
Just precalculate factorial from 1 to 10^6 in an array say fact[ ] and for each query n , print fact[n]

it would go something like this

fact[0] = 1;

for(int i=1;i<=1000000;i++)
fact[i] = (fact[i-1] * i) % mod

you will pre-calculate only once and each query can be answered in O(1) time

2 Likes
8

thanks.i’ll try.

9

Thanks a lot @waqar_ahmad224.
Had to use fastio with precomputation.

Bytheway i love your youtube videos.

10

Whenever you have large numbers, remember the following.

Fundamental operations give same answer with both pre and post modulation.

(a+b)% mod = (a%mod + b%mod)%mod;
(a*b)%mod = (a%mod * b%mod)%mod;
You get the idea.
By doing modulation at every position, we prevent overflow of the number.
a%mod & b%mod are not necessary, that has to be done based on your requirements.

1 Like
11

you’re welcome @lost_boy12 , and good luck for your next challenge

1 Like