LESSON 143 OF 414 · LOOPS & GLOBAL VARIABLES

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

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:

var 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:

var fact = 1   // fact is initially 1 = 1!
for (i <- 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:

var fact = 1
for (i <- 1 to 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

Guided

Ctrl + Enter to check

Factorial in Scala, explained

Problem overview

The method factorial receives a non-negative integer n and returns n!, the product 1 * 2 * 3 * ... * n. For n = 5 the product is 1 * 2 * 3 * 4 * 5 = 120. By convention 0! is 1, because an empty product is 1.

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

Approach: a running product

You can compute the result without any collection or recursion. Keep one variable, start it at 1, and multiply it by each number from 1 to n. After the multiplication by k, the variable holds k!. For n = 4 it goes through 1, 2, 6 and 24.

This is the same accumulator pattern as a running sum, with two differences: the operation is multiplication, and the starting value is 1, not 0. Multiplying by 1 changes nothing, so 1 is the neutral start. Starting at 0 would leave the product at 0 forever.

The loop makes n multiplications and uses a fixed number of variables, which meets both limits in the statement.

A recursive definition, n! = n * (n - 1)!, is also correct, but it keeps one call on the stack for each step and would need O(n) space. The loop is what makes the O(1) space limit possible.

A small hand check helps before you type anything. For n = 3, the variable goes 1, then 1 * 1 = 1, then 1 * 2 = 2, then 2 * 3 = 6. If your trace agrees with the definition, the loop is right.

Step by step

Declare fact with var and set it to 1. The loop updates it, so it can't be a val.
Loop with for (i <- 1 to n). The range 1 to n includes both ends, so every factor of n! is visited exactly once. For n = 0 the range is empty.
Multiply with fact *= i. This is shorthand for fact = fact * i.
Return fact. The method returns only after the loop has finished, so the value is complete.

The solution in Scala

class Solution {
    def factorial(n: Int): Int = {
        var fact = 1
        for (i <- 1 to n) {
            fact *= i
        }
        return fact
    }
}

Tracing n = 5:

`i`	`fact` afterwards
1	1
2	2
3	6
4	24
5	120

Language details

Scala infers Int for fact from the literal 1. The method's return type is also Int.
1 to n includes n. 1 until n would stop one short and drop the last factor.
The compound assignment *= only works on a var. On a val the compiler rejects it, because a val can't be reassigned.

Complexity

The loop body runs n times and each run is one multiplication, so the time is O(n). The method keeps fact and the loop variable and nothing that grows with n, so the extra space is O(1).

Edge cases and common mistakes

n = 0. The loop doesn't run and the method returns the starting value 1, which is the right answer for 0!.
Starting fact at 0. Every product is then 0.
Int overflow. Factorials grow very fast, and an Int is 32 bits. factorial(12) returns 479001600, the largest factorial that fits. factorial(13) returns 1932053504, which is wrong: the true value is 6227020800. factorial(20) returns -2102132736. Scala does not raise an error on overflow, it wraps silently. A Long would extend the range up to 20!.
Returning inside the loop. A return in the loop body would end the method after the first pass.

Testing

Small inputs worth trying: 0 gives 1, 1 gives 1, 2 gives 2, 5 gives 120 and 10 gives 3628800.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free