Start learning free

LESSON 137 OF 347 · LOOPS & GLOBAL VARIABLES

Factorial in C#: A Loop That Builds the Product

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

    C# · LOOPS & GLOBAL VARIABLES

    Factorial in C#, explained

    Problem overview

    The method Factorial(int n) takes a non-negative integer n and returns n!, the product of every whole number from 1 up to n. For n = 5 that is 1 * 2 * 3 * 4 * 5 = 120.

    The statement asks for O(n) time and O(1) extra space. That means one pass over the numbers 1 to n, and a fixed number of variables no matter how large n is.

    Approach: a running product

    You can't compute a product in one step, but you can build it gradually. Keep a variable that holds the product so far, and multiply it by each factor in turn. For n = 4 it changes like this:

    start:      fact = 1
multiply 1: fact = 1
multiply 2: fact = 2
multiply 3: fact = 6
multiply 4: fact = 24

    Each intermediate value is itself a factorial (1!, 2!, 3!, 4!), so when the last factor has been multiplied in, fact holds the answer. A for loop is the natural tool because the number of repetitions is known in advance: exactly n.

    Step by step

    1. Declare fact and set it to 1. The starting value must be 1, not 0, because multiplying anything by 0 gives 0. Starting at 1 also makes the case n = 0 work without special handling: the loop doesn't run, and the method returns 1, which is the correct value of 0!.
    2. Loop with i from 1 through n. The condition is i <= n, with <=, so that n itself is included as a factor. The loop starts at 1 rather than 0, since a factor of 0 would wipe out the product.
    3. Multiply inside the loop. fact *= i is shorthand for fact = fact * i.
    4. Return fact after the loop. The return belongs below the closing brace. Placed inside the loop, it would end the method after the first factor.

    The solution in C#

    class Solution {
    public int Factorial(int n) {
        int fact = 1;
        for (int i = 1; i <= n; i++) {
            fact *= i;
        }
        return fact;
    }
}

    A few C# details are worth knowing:

    • The loop header has three parts. int i = 1 runs once at the start, i <= n is tested before every pass, and i++ runs after every pass. The variable i exists only inside the loop, while fact, declared before it, is still available at the return.
    • int overflow is silent. An int is a 32-bit number whose largest value is 2,147,483,647. By default, C# arithmetic that goes past the limit wraps around without an exception and without a warning. Factorial(12) is 479001600, which fits. Factorial(13) should be 6,227,020,800, but the method returns 1932053504, a wrong number that looks perfectly normal.
    • Bigger results need a bigger type. Declaring fact as long pushes the limit up to 20!, and System.Numerics.BigInteger has no practical limit. This lesson's signature uses int, so its tests stay in the range where int is enough.

    Complexity

    Time: O(n). The loop runs exactly n times, and each pass does one multiplication, which takes constant time.

    Space: O(1). The method only uses fact, i and the parameter n. Nothing grows with the input.

    Edge cases and common mistakes

    • n = 0. The answer is 1. It works because fact starts at 1 and the loop body never runs. Starting fact at 0 would return 0 for every input.
    • n = 1. The loop runs once and multiplies 1 by 1, so the answer is 1.
    • Using i < n. The last factor is then missing, and Factorial(5) returns 24 instead of 120.
    • Starting the loop at 0. Then fact is multiplied by 0 on the first pass and stays 0.
    • Returning inside the loop. The method would stop after the first pass and return 1.
    • Overflow for n above 12. The result wraps silently, as described above.

    Testing

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