Factorial Algorithm Tutorial

Factorial with Modular Arithmetic

A factorial of $n$ (written $n!$) is the product of all positive integers up to $n$. When factorials grow large, you compute the result modulo $10^9 + 7$ to prevent overflow.

Factorial values grow quickly. For $n = 20$, you already exceed $10^{18}$. You can take the modulo at each step because $(a \times b) \mod m = ((a \mod m) \times (b \mod m)) \mod m$.

function factorial(n, mod):
    result = 1
    for i from 1 to n:
        result = (result * i) mod mod
    return result

Precomputation: If you need factorials for multiple queries, precompute them in an array:

function precomputeFactorials(maxN, mod):
    fact = array of size maxN + 1
    fact[0] = 1
    for i from 1 to maxN:
        fact[i] = (fact[i-1] * i) mod mod
    return fact

Applications: You use factorials for permutations, combinations, probability calculations, and counting problems in combinatorics.

Time complexity: $O(n)$ for a single factorial computation.

Space complexity: $O(1)$ for iterative approach, $O(n)$ if precomputing an array.