LESSON 138 OF 348 · LOOPS & GLOBAL VARIABLES

Factorial in Kotlin: A for Loop Over 1..n in O(n) Time

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

Guided

Ctrl + Enter to check

Factorial in Kotlin, explained

Problem overview

The function factorial receives a non-negative integer n and returns n!, the product of every whole number from 1 to n. The lesson sets a budget of O(n) time and O(1) extra space.

In the example, n = 5, and 1 * 2 * 3 * 4 * 5 is 120, so the function returns 120. By convention 0! is 1, and the same code gives that answer without a special case.

Approach: build the product one factor at a time

Multiplying by hand, you would keep a running total and fold in each number in turn: start at 1, multiply by 2, then by 3, and so on up to n. The code does exactly that. A single variable holds the product so far, and a loop visits each factor once.

The loop runs n times, so the time is O(n). Only the product and the loop counter are stored, so the extra space is O(1).

Here is the state of fact for n = 4, one loop pass at a time: it starts at 1, becomes 1 when i is 1, then 2 when i is 2, then 6 when i is 3, and finally 24 when i is 4. Each value is the factorial of the i just processed, which is why the loop can stop at n and return what it holds.

Other approaches exist. A recursive function calls itself with n - 1 and multiplies the result by n, but it uses O(n) stack space. The loop avoids that and meets the O(1) space budget.

Step by step

Declare the running product as var fact = 1. It has to be a var because it changes on every pass, and it starts at 1 because 1 is the neutral element of multiplication: multiplying by it changes nothing. Starting at 0 would leave the answer stuck at 0.
Loop over the factors with for (i in 1..n). The range 1..n includes both ends, so i takes every value from 1 to n. Kotlin declares i for you, with no var or type.
Multiply inside the loop with fact *= i, which is shorthand for fact = fact * i.
Return fact after the loop, once every factor has been folded in.

The solution in Kotlin

class Solution {
    fun factorial(n: Int): Int {
        var fact = 1
        for (i in 1..n) {
            fact *= i
        }
        return fact
    }
}

A few Kotlin details matter here:

Ranges are inclusive. 1..n contains n. If you want to stop before the end, write 1 until n. Using until here would leave out the last factor and return 24 for n = 5.
An empty range is fine. When n is 0, the range 1..0 has no elements, so the loop body never runs and the function returns the initial 1. That is the correct value of 0!.
Int is 32 bits. It holds values up to 2,147,483,647, and overflow wraps around silently instead of raising an error. factorial(12) returns 479001600, but factorial(13) returns 1932053504 rather than the true 6227020800, and factorial(20) returns the negative number -2102132736. With Long the same loop is exact up to 20!, which is 2432902008176640000. The lesson's signature uses Int, so the tests stay within its range.
val would not compile. A val can't be reassigned, so fact *= i needs var.

Complexity

Time: O(n). The loop body is one multiplication and runs once for each value from 1 to n.

Space: O(1). The function keeps fact and i and nothing that grows with n.

Edge cases and common mistakes

n = 0. Returns 1, because the loop doesn't run.
n = 1. Returns 1, since the loop multiplies 1 by 1.
Starting fact at 0. Every product stays 0.
Forgetting the return. A Kotlin function with a declared Int return type and no return on every path is a compile error.
Using until instead of ... The loop stops one factor early.
Large inputs. Beyond 12, Int results are wrong because of overflow, as shown above.

Testing

n = 5 gives 120.
n = 0 gives 1.
n = 1 gives 1.
n = 12 gives 479001600.

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

Start learning free