Start learning free

LESSON 143 OF 415 · LOOPS & GLOBAL VARIABLES

Factorial in Swift: O(n) Loop and Half-Open Range

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

    SWIFT · LOOPS & GLOBAL VARIABLES

    Factorial in Swift, explained

    Problem overview

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

    The lesson asks for O(n) time and O(1) extra space. One loop and one running product are enough to meet both limits.

    Approach: build the product one factor at a time

    Start with a product of 1 and fold in each factor in turn. For n = 4 the product goes 1, 2, 6, 24: after multiplying by i, it holds i!. A loop from 1 to n repeats the same multiplication, so the code never needs to know n in advance.

    The starting value of 1 matters. It is the identity for multiplication, so it changes nothing on the first step, and it is also the correct answer for n = 0, because 0! is defined as 1 and the loop then has nothing to do.

    Traced for n = 5: fact starts at 1, then the loop multiplies it by 1, 2, 3, 4 and 5 in turn, giving 1, 2, 6, 24 and finally 120. The multiplication by 1 on the first pass is harmless, so starting the loop at 1 is fine.

    Step by step

    1. Declare the running product. Call it fact, make it a var because it changes on every pass, and start it at 1. Swift infers the type Int from the literal.
    2. Loop over the factors. Use i over the half-open range 1..<(n + 1), which covers 1 up to and including n.
    3. Multiply inside the loop. fact *= i folds the current factor into the product.
    4. Return fact after the loop, when every factor has been used.

    The solution in Swift

    class Solution {
    func factorial(_ n: Int) -> Int {
        var fact = 1
        for i in 1..<(n + 1) {
            fact *= i
        }
        return fact
    }
}

    Swift details worth knowing:

    • Two range operators. a..<b stops before b, and a...b includes b. Writing 1...n looks more natural, but a closed range needs its lower bound to be at most its upper bound. With n = 0 the range 1...0 is invalid, and the program crashes at run time. The half-open 1..<1 is just empty, which is why the solution writes 1..<(n + 1).
    • var versus let. A let constant can't change. Declaring fact with let makes fact *= i a compile error: the left side of the mutating operator isn't mutable.
    • Overflow traps. Int is 64 bits. Arithmetic that doesn't fit doesn't wrap around: the program stops with a crash. factorial(20) returns 2432902008176640000, which fits, but factorial(21) would exceed the largest Int and crash.
    • The label _. The parameter is declared _ n, so callers write factorial(5) without a label.

    Complexity

    Time: O(n). The loop runs exactly n times and each pass does one multiplication.

    Space: O(1). The function keeps only fact and the loop variable, whatever the size of n.

    Edge cases and common mistakes

    • n = 0. The loop doesn't run and the function returns 1, which is correct.
    • n = 1. The loop multiplies by 1 once and the result is 1.
    • Starting at 0. A product that starts at 0 stays 0 forever.
    • Stopping one factor early. 1..<n leaves out n itself, so factorial(5) would give 24 instead of 120.
    • Returning inside the loop. The function would end after the first factor.
    • Large inputs. Any n above 20 overflows Int and crashes.

    Testing

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