Factorial in Scala

Input: n = 5
Output: 120
Explanation: 5! = 1 * 2 * 3 * 4 * 5 = 120

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).