Factorial - Algorithm Tutorial | Repovive

##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######

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$ .

text

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:

text

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.

Factorial Algorithm Tutorial

Learn

Factorial with Modular Arithmetic

Implement this Algorithm

Related Algorithms