Start learning free

LESSON 140 OF 410 · LOOPS & GLOBAL VARIABLES

Factorial in JavaScript: Loop, Recursion and BigInt

Practice Read the full explanation

Given a non-negative integer n return the factorial of n, also denoted as n!

n! = 1 * 2 * 3 * ... * (n - 1) * n

Example:

Input: n = 5
Output: 120
Explanation: 5! = 1 * 2 * 3 * 4 * 5 = 120

Note:

Your algorithm should run in O(n) time and use O(1) space.


Hints:

To compute the factorial, we have to iterate through every value from 1 to n and multiply that value to the product. How can we achieve this?

First of all, we should store this product somewhere as we compute it. That 'somewhere' is a variable, let's name it fact. For example, for n = 4: 
set fact to 1       (fact is initially 1 = 1!)
multiply fact by 2  (now fact is 1 * 2 = 2!)
multiply fact by 3  (now fact is 1 * 2 * 3 = 3!)
multiply fact by 4  (now fact is 1 * 2 * 3 * 4 = 4!)
How can we extend this code to compute the factorial of any value of n?

With a loop! Let's use a for loop and a variable i to iterate through the numbers 1 to n: 
set fact to 1       (fact is initially 1 = 1!)
for i from 1 to n:
	(what should we do here?)
What should we do inside this loop?

Inside the loop, all we should do is multiply fact by i.
When the loop terminates, the answer lies in fact: 
set fact to 1
for i from 1 to n:
	multiply fact by i
return fact


We have a for loop that performs exactly n iterations, thus the Time Complexity is O(n).
The only extra space we use is the variable fact and the iterator variable i inside the loop, thus the Extra Space used is O(1).

Video Solution:

STEP 1 OF 4
    Ctrl + Enter to check

    JAVASCRIPT · LOOPS & GLOBAL VARIABLES

    Factorial in JavaScript, explained

    Problem overview

    The factorial of a non-negative integer n, written n!, is the product of all whole numbers from 1 to n. The method factorial(n) returns that product. For n = 5 the result is 1 * 2 * 3 * 4 * 5 = 120.

    By definition 0! is 1, because a product with no factors is 1. The lesson asks for O(n) time and O(1) space.

    How to calculate a factorial in JavaScript

    The idea is a running product. Start with 1, then multiply by 1, by 2, and so on up to n. For n = 4:

    fact = 1
fact = 1 * 1 = 1     (1!)
fact = 1 * 2 = 2     (2!)
fact = 2 * 3 = 6     (3!)
fact = 6 * 4 = 24    (4!)

    A for loop does this for any n. The running product is a variable that the loop updates, so it has to be declared with let, not const.

    Step by step

    1. Declare fact and set it to 1. 1 is the starting value for a product, and it makes n = 0 work: the loop never runs, and 1 is returned.
    2. Write a for loop with i from 1 while i <= n. The <= includes n itself. Every factor from 1 through n is visited once.
    3. Multiply inside the loop. fact *= i is short for fact = fact * i.
    4. Return fact after the loop.

    The solution in JavaScript

    class Solution {
    factorial(n) {
        let fact = 1;
        for (let i = 1; i <= n; i++) {
            fact *= i;
        }
        return fact;
    }
}

    The loop runs exactly n times, so the time is O(n). It only stores fact and i, so the extra space is O(1).

    Factorial grows fast

    JavaScript numbers are 64-bit floating-point values. They store whole numbers exactly only up to Number.MAX_SAFE_INTEGER, which is 9007199254740991. Factorials pass that limit quickly:

    • 18! is 6402373705728000, still a safe integer.
    • 19! is 121645100408832000, which is larger than the safe limit, so results from here on can't be trusted to be exact.
    • 22! already prints in exponent form: 1.1240007277776077e+21.
    • 170! is about 7.257415615307994e+306, the largest factorial a number can hold. 171! comes out as Infinity.

    For exact large results, use BigInt. Its literals end in n, and it can't be mixed with ordinary numbers in arithmetic:

    function factorialBig(n) {
    let fact = 1n;
    for (let i = 1n; i <= BigInt(n); i++) {
        fact *= i;
    }
    return fact;
}

console.log(factorialBig(20));
console.log(factorialBig(25));

    2432902008176640000n
15511210043330985984000000n

    The ordinary-number loop prints 1.5511210043330986e+25 for 25!, which is only an approximation of the same value.

    The recursive version

    Factorial also has a recursive definition: n! = n * (n - 1)!, with 0! = 1 and 1! = 1.

    const factorial = n => (n <= 1 ? 1 : n * factorial(n - 1));

console.log(factorial(5));

    120

    It gives the same results, but it also takes O(n) space for the call stack, and a very large n such as 1e6 throws RangeError: Maximum call stack size exceeded. The loop avoids both problems, which is why the lesson uses it.

    Edge cases and common mistakes

    • n = 0. Returns 1, because fact starts at 1 and the loop doesn't run.
    • Starting fact at 0. Every product would be 0.
    • Starting the loop at 0. Multiplying by i = 0 turns the product into 0 for every n.
    • Using i < n. It leaves out the last factor: factorial(5) would give 24.
    • Negative numbers. Factorial isn't defined for them. This code returns 1 for -3, because the loop condition is false at once. Check for it first if your input can be negative.
    • Time complexity. It is O(n) multiplications, counting each as one step. The numbers themselves get large, so with BigInt each multiplication takes longer as the result grows.

    Testing

    • factorial(0) gives 1.
    • factorial(1) gives 1.
    • factorial(5) gives 120.
    • factorial(10) gives 3628800.
    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free