Boring Factorials

Easy

0/40

Average time to solve is 15m

Contributed by

44 upvotes

Asked in company

Problem statement

You are given an integer ‘N’ and a prime number ‘P’. Your task is to find the N! modulo P.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first and only line of each test case contains two integers, ‘N’, and ‘P’ in that order, where N is the integer and P is a prime number.

Output Format :

For each test case, print the “N! % P”, as described in the problem statement.

Output for each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^9
1 <= P <= 10^9
|N - P| <= 1000

Time Limit: 1 sec

Sample Input 1 :

2
5 3
4 5

Sample Output 1 :

0
4

Explanation For Sample Input 1 :

Test Case 1:
5! = 5*4*3*2*1 = 120 and and it will give remainder as 0 when divided by 3.

Test Case 2:
4! = 4*3*2*1 = 24 and it will give the remainder 4 when divided by 5.

Sample Input 2 :

2
5 11
10 7

Sample Output 2 :

10
0

Hint 1

Hint 2

Try to use the brute-force with %p in each iteration.

Approaches (2)

Approach 1

Approach 2

Brute-Force

The idea here is to use the brute force approach.
One can think of computing the N! first and then find its modulo P. But this can lead to the overflow problem as the N! can be a very large number. So, computing N! and then using % is not a good idea.
We can overcome this problem by using the modulo operator at each iteration. In other words, we multiply one by one with ‘i’ under modulo ‘P’.
Declare a variable ans = 1.
Run a loop from i = 1 to i <= N, in each iteration do:
- ans = (ans * i) % P
Return the ans.

Time Complexity

O(N), where 'N; is the number given in the problem.

We are finding the factorial of ‘N’ using the loop from ‘1’ to ‘N’. Hence, the overall time complexity will be O(N).

Space Complexity

O(1).

As we are only using the constant extra space.

(100% EXP penalty)

Boring Factorials

Console