Start learning free

LESSON 147 OF 414 · LOOPS & GLOBAL VARIABLES

Factorial in Rust: A for Loop in O(n) Time and O(1) Space

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

    RUST · LOOPS & GLOBAL VARIABLES

    Factorial in Rust, explained

    Problem overview

    The function factorial takes a non-negative integer n and returns n!, the product of all whole numbers from 1 to n. For n = 5, 5! = 1 * 2 * 3 * 4 * 5 = 120.

    The statement sets a budget of O(n) time and O(1) extra space. A single loop with one running product fits it. By convention 0! is 1, because a product with no factors is 1.

    Approach

    Build the product one factor at a time. A variable fact starts at 1, since multiplying by 1 changes nothing. For n = 4 its values are:

    1. Start: fact is 1, which is 1!.
    2. Multiply by 2: fact is 2, which is 2!.
    3. Multiply by 3: fact is 6, which is 3!.
    4. Multiply by 4: fact is 24, which is 4!.

    The repeated multiplication is a loop over the numbers 1 to n. Each pass multiplies the current number into fact, and after the last pass fact holds n!.

    The accumulator starts at 1, not 0. A product that starts at 0 would stay 0 whatever was multiplied into it.

    Step by step

    1. Declare fact as mutable, starting at 1. Rust variables are immutable by default, and this one changes on every pass, so it is written let mut fact = 1;.
    2. Loop over 1 to n inclusive. The range 1..=n includes n, which is the last factor. The range 1..n would leave it out.
    3. Multiply inside the loop. fact *= i; folds the current factor into the running product.
    4. Return fact once the loop is over.

    The solution in Rust

    impl Solution {
    fn factorial(n: i32) -> i32 {
        let mut fact = 1;
        for i in 1..=n {
            fact *= i;
        }
        return fact;
    }
}

    Some Rust details here:

    • Inclusive range. 1..=n counts from 1 to n and includes both ends. If n is 0, the range is empty and the loop runs zero times, so the function returns 1, the correct value of 0!.
    • Type inference. The compiler gives fact the type i32, since it is returned from a function whose return type is i32.
    • *= is shorthand for fact = fact * i, and it needs mut.
    • Return. return fact; works, and so does the bare expression fact as the last line without a semicolon.

    Complexity

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

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

    Edge cases and common mistakes

    • n = 0. The result is 1. The loop does not run, and fact keeps its initial value.
    • n = 1. The result is 1.
    • Starting fact at 0. Every product would be 0.
    • Using 1..n. The last factor is missing, so factorial(5) would return 24 instead of 120.
    • Overflow. Factorials grow quickly. An i32 holds 12! = 479,001,600 but not 13! = 6,227,020,800. In an optimized build, which is how the lessons are compiled, the multiplication wraps silently: factorial(13) returns 1932053504 and factorial(20) returns -2102132736. A debug build would panic with an overflow error instead. Inputs up to 12 are safe.

    Testing

    • n = 5 gives 120.
    • n = 0 gives 1.
    • n = 1 gives 1.
    • n = 4 gives 24.
    • n = 12 gives 479001600.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free