PPractick

The problem

A combinatorics module needs N!, the number of ways to arrange N distinct items, for N up to 10^5. Factorials explode: 13! already exceeds a 32-bit int, and 21! exceeds 64 bits. So, like most competitive-programming and interview problems, the answer is asked modulo 10^9 + 7. The recursive definition N! = N × (N − 1)! with 0! = 1 maps directly onto code; the details that matter are applying the modulo at every step and using 64-bit multiplication so the intermediate product can't overflow.

Example: 5! = 120; 13! mod (10^9 + 7) = 227020758.

Function signature

long long factorialMod(int n);  // n! mod 1,000,000,007

Test cases

Input n	Output	Explanation
0	1	0! = 1 by definition
1	1
5	120
10	3628800	Still below the modulus
13	227020758	13! = 6227020800 exceeds INT_MAX, so the modulo kicks in
20	146326063	20! = 2432902008176640000, reduced mod 10^9 + 7

(Confirm: 0 ≤ n ≤ 10^5; the answer is n! mod 1,000,000,007.)

How interviewers phrase it

• "Compute the factorial of N using recursion."
• "Return N! modulo 10^9 + 7" (GeeksforGeeks and most online judges).
• Follow-ups often lead to nCr modulo a prime, which needs factorials and modular inverses.

Clarifying questions to ask

1. How large can N be? (Overflow and recursion depth.)
2. Should the result be taken modulo something?
3. Is recursion required, or is iteration fine?

Follow-ups to expect

1. "Why take the modulo at every step, not just at the end?"
2. "Why is the product computed in 64 bits?"
3. "Why 10^9 + 7?"
4. "Recursion depth for N = 10^5?"
5. "How would you compute nCr mod p?"

Related questions

• Sum of First N Numbers Easy
• Understand recursion by print something N times Easy
• Print name N times using recursion Easy
• Print 1 to N using Recursion Easy
• Print N to 1 using Recursion Easy
• Reverse an array Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in