Long Factorials

Calculating the factorials is one of the most basic algorithms out there. It’s so basic it’s actually used to teach a harder concept, recursion. I’m explaining this so that I can get away with using the 2-minute explanation of both concepts. Let me know if you’d be interested in a deeper dive.

Recursion

Recursion, the repeated application of a recursive procedure i.e. a function calling itself. The joke goes “To understand recursion you must first understand recursion.”

Factorial

A factorial of a number is the product of all positive integers less than or equal to that number. The thing with factorials, however, is that they tend to get very large very fast and the large the numbers the slower they perform.

For example

• 4! = 4 x 3 x 2 x 1 = 24
• 10! = 3628800
• 15! = 1.3076744e+12

I wasn’t kidding about the 2 minute explanations.

The Problem

Write an efficient function that calculates and displays extra long factorials.

Expected Output

A really long number that isn’t in exponential form

Restrictions

• 1 <= n <= 100

My Solution

This honestly didn’t require much thought because it’s so easy. The first requirement to get large numbers. To do this all you have to do is cast your input to BigInt and you’re gold.

BigInt(n) or add an n to the end of an integer literal, e.g. 1n.

The second requirement is about efficiency. The biggest cause of the slowdown is that we calculate the factorials of lower numbers multiple times. This is a waste of time because the result is not going to change. So after the first calculation, we really shouldn’t be doing it again. As a result, if we cache those calculations, our performance goes up dramatically. This concept is called memoization and is a fun read.

function longFactorials(n) {
    const cache = new Map()
    const factorial = n => {
        if (n == 0){
            return 1n
        }
        if (cache.has(n)) {
            return cache.get(n)
        } else {
            const x = BigInt(n) * factorial(n - 1)
            cache.set(n, x)
            return x
        }
    }
    return factorial(n).toString()
}

Not too complicated right? This solution passes all tests didn’t kill any brain cells.