Start learning free

LESSON 138 OF 338 · LOOPS & GLOBAL VARIABLES

Factorial in Go: O(n) Iterative 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

    GO · LOOPS & GLOBAL VARIABLES

    Factorial in Go, explained

    Problem overview

    The function factorial receives a non-negative integer n and returns n!, the product 1 * 2 * 3 * ... * n. For n = 5 the answer is 1 * 2 * 3 * 4 * 5 = 120. By convention, 0! is 1: the product of no numbers is 1.

    The statement asks for O(n) time and O(1) extra space.

    Approach: build the product one factor at a time

    Keep a variable fact that holds the product so far. Start it at 1, because multiplying by 1 changes nothing, so it is the right starting point for a product, just as 0 is for a sum. Then walk i from 1 to n and multiply fact by i each time.

    For n = 4, fact goes 1, then 1, 2, 6, 24: after the pass for i = 1 it is 1!, after i = 2 it is 2!, after i = 3 it is 3!, and after i = 4 it is 4!. Each pass extends the previous factorial by one factor.

    Step by step

    1. Declare fact with := and the value 1.
    2. Loop with i from 1 through n, so that each factor of n! is used exactly once. The condition is i <= n.
    3. Multiply inside the loop: fact *= i.
    4. Return fact after the loop.

    The solution in Go

    func factorial(n int) int {
    fact := 1
    for i := 1; i <= n; i++ {
        fact *= i
    }
    return fact
}

    Go details:

    • *= is short for fact = fact * i.
    • Fixed-size integers. Go's int is 64 bits here. Factorials grow fast, and the largest one that fits is 20!, which is 2432902008176640000. Past that, Go does not report an error: the multiplication wraps around silently. Running this function, factorial(21) gives -4249290049419214848, a negative number. Tests with larger inputs would need the math/big package.
    • The empty loop. For n = 0, the condition 1 <= 0 is false, the body never runs, and the function returns the initial 1, which is the correct value of 0!.
    • No recursion needed. A recursive version is possible, but a loop uses constant stack space, which fits the stated O(1) space.

    Why the starting value is 1

    An accumulator must start at a value that doesn't disturb the first operation. For a sum, that is 0, since 0 + x is x. For a product, it is 1, since 1 * x is x. Starting fact at 0 would turn every product into 0, and the loop would look correct while always answering 0. The same reasoning explains 0! = 1: with no factors to multiply, the result is the starting value.

    Tracing n = 5

    Start with fact equal to 1. The pass for i = 1 keeps it at 1, i = 2 makes it 2, i = 3 makes it 6, i = 4 makes it 24, and i = 5 makes it 120. The loop ends because 6 is not less than or equal to 5, and the function returns 120.

    Complexity

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

    Space: O(1). Only fact and i are stored.

    Edge cases and common mistakes

    • n = 0. The answer is 1, not 0. Starting fact at 0 would make every result 0.
    • n = 1. One pass multiplies 1 by 1, so the result is 1.
    • Starting the loop at 0. The first multiplication would turn fact into 0, and it would stay 0.
    • Using i < n. The last factor would be missing: n = 5 would give 24.
    • Overflow past 20. factorial(20) is correct, while factorial(21) wraps to a wrong, negative value.
    • Declaring fact inside the loop. It would be reset on every pass and out of scope for the return.

    Testing

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