Start learning free

LESSON 138 OF 348 · LOOPS & GLOBAL VARIABLES

Factorial in TypeScript: O(n) Time and O(1) Space with a Loop

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: 
fact = 1   # fact is initially 1 = 1!
fact *= 2   # now fact is 1 * 2 = 2!
fact *= 3   # now fact is 1 * 2 * 3 = 3!
fact *= 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: 
fact = 1   # fact is initially 1 = 1!
for i : 1 -> 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: 
fact = 1
for i : 1 -> n:
	fact *= 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

    TYPESCRIPT · LOOPS & GLOBAL VARIABLES

    Factorial in TypeScript, explained

    Problem overview

    The method factorial receives a non-negative integer n and returns n!, the product 1 * 2 * 3 * ... * n. For n = 5 that is 1 * 2 * 3 * 4 * 5 = 120.

    The statement asks for O(n) time and O(1) extra space. A single loop with one running product meets both limits.

    Approach: multiply as you count

    Build the product one factor at a time. Start with a variable holding 1, then walk through the numbers 1, 2, ..., n and multiply each into it. After the factor 2 the variable holds 2, after 3 it holds 6, and after 4 it holds 24. The last multiplication gives the answer.

    The variable must start at 1, not 0. Multiplying by 1 changes nothing, so 1 is the neutral starting value for a product, just as 0 is for a sum. Starting at 0 would keep the product at 0 forever.

    Step by step

    1. Declare fact as a number starting at 1. It holds the product so far and is declared with let because it changes on every pass.
    2. Loop with i from 1 through n. The condition i <= n makes sure that n itself is one of the factors. Each integer in that range is visited once.
    3. Multiply inside the loop. fact *= i replaces fact with fact * i, adding one more factor to the product.
    4. Return fact after the loop, once all the factors are in.

    The solution in TypeScript

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

    Notes on the TypeScript side:

    • One number type. TypeScript has no separate integer type, so fact, i and the result are all number, a double-precision float. There is no integer overflow, but there is a limit on exactness, described below.
    • Type annotations disappear. The : number markers help the compiler and your editor. They are removed when the code is compiled to JavaScript, and they do not convert anything while the program runs.
    • The loop variable is local. let i exists only inside the for statement.
    • No recursion needed. A recursive version, n * factorial(n - 1), is also correct, but it uses a stack frame per call and so O(n) space. The loop keeps the space constant.

    Complexity

    Time: O(n). The loop runs exactly n times, with one multiplication per pass.

    Space: O(1). Only fact and i are stored, however large n is.

    Edge cases and common mistakes

    • n = 0. By definition 0! is 1. The loop does not run, and the method returns the starting value, 1, which is correct. This is one more reason to start fact at 1.
    • n = 1. The loop runs once, multiplying 1 by 1, and the result is 1.
    • Starting fact at 0. Every product would be 0.
    • Using < instead of <=. The factor n would be missing, so factorial(5) would return 24.
    • Large results. Factorials grow very fast. factorial(18) is 6402373705728000, which a number holds exactly, but integers above 2^53 (about 9 * 10^15) are not all representable. For factorial(22) the method returns 1.1240007277776077e+21, a rounded value in exponent notation. At factorial(171) the product is too big for any number and the result is Infinity, while factorial(170) still gives about 7.257415615307994e+306. When exact huge factorials matter, JavaScript's BigInt type is the tool for it.

    Testing

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