Factorial

Q: What is the time complexity of computing a factorial?

Both the loop and the recursion do one multiplication per number up to n : O(n) time. The loop needs O(1) extra space. The recursion keeps one stack frame per call until the base case returns, so it uses O(n) space.

Q: Why is 0! equal to 1?

0! is the product of no numbers, and a product with no factors is 1 , the same way a sum with no terms is 0 . It also keeps n! = n × (n-1)! true at n = 1 . And there is exactly one way to arrange zero items.

Q: What is the largest factorial that fits in an integer?

12! = 479001600 is the largest factorial that fits in a signed 32-bit integer. 20! = 2432902008176640000 is the largest for a signed 64-bit integer. Beyond that you need numbers of unlimited size, such as Python's int , Java's BigInteger or JavaScript's BigInt .

BeginnerMath and simulation Recursion

+10

The factorial of a whole number n, written n!, is the product of every whole number from 1 up to n. For example, 4! = 1 × 2 × 3 × 4 = 24. By definition 0! = 1. Your function gets n and returns n!.

Function

factorial(n: integer) → integer

ninteger: the whole number whose factorial you compute
Returnsinteger: the product of every whole number from 1 to n, which is 1 when n is 0

Constraints

0 ≤ n ≤ 12
The answer fits in a signed 32-bit integer: the largest one is 12! = 479001600.

Examples

Input: n = 5
Output: 120
Explanation: Multiply 1 × 2 × 3 × 4 × 5. The running product goes 1, 2, 6, 24 and ends at 120.

Input: n = 0
Output: 1
Explanation: There is nothing to multiply, and a product with no factors is 1. That is why 0! = 1.

Follow-up

100! has 158 digits. Can you count how many zeros it ends with without computing it?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A factorial has two equivalent descriptions, and each one becomes code. As a product, n! = 1 × 2 × ... × n is a loop. As a recursive definition, 0! = 1 and n! = n × (n-1)! is a function that calls itself. Both do about n multiplications; the loop needs no call stack.

Recursion from the definition

Intuition

If you know 4! = 24, then 5! = 5 × 24 = 120. So factorial(n) asks for factorial(n-1) and multiplies the answer by n. The base case factorial(0) returns 1 without a call. From 5 the calls go down 5, 4, 3, 2, 1, 0, and the answers come back up: 1, 1, 2, 6, 24, 120.

There are n + 1 calls and n multiplications: O(n) time. Each call waits on the stack for the one below it, so the stack holds n + 1 frames, O(n) space.

Algorithm

If n is 0, return 1. This is the base case.
Otherwise call the function on n-1.
Multiply that result by n and return it.

def factorial(n):
    if n == 0:
        return 1  # base case: 0! = 1
    return n * factorial(n - 1)

Multiply in a loop

Intuition

Unroll the recursion into a running product: start at result = 1 and multiply by 2, then 3, and so on up to n. Starting at 1 covers n = 0 and n = 1 too: the loop from 2 to n runs zero times and returns 1, the right answer for both.

That is n-1 multiplications, O(n) time, and one number, O(1) space, with no call stack to overflow.

Algorithm

Set result = 1.
Loop k from 2 to n, both included.
Multiply result by k on every step.
Return result.

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Pitfalls and edge cases

Starting the product at 0. Every multiplication keeps it at 0, so start at 1.
Stopping the recursion at n == 1 only. Called with 0, the function goes on to -1, -2 and so on until the stack overflows. Make n == 0 the base case.
Looping with k < n instead of k ≤ n. That leaves out the last factor, so 5 gives 24 instead of 120.
In Swift, writing for k in 2...n. A closed range whose end is below its start crashes at run time when n is 0 or 1.

Frequently asked questions3

What is the time complexity of computing a factorial?

Both the loop and the recursion do one multiplication per number up to n: O(n) time. The loop needs O(1) extra space. The recursion keeps one stack frame per call until the base case returns, so it uses O(n) space.

Why is 0! equal to 1?

0! is the product of no numbers, and a product with no factors is 1, the same way a sum with no terms is 0. It also keeps n! = n × (n-1)! true at n = 1. And there is exactly one way to arrange zero items.

What is the largest factorial that fits in an integer?

12! = 479001600 is the largest factorial that fits in a signed 32-bit integer. 20! = 2432902008176640000 is the largest for a signed 64-bit integer. Beyond that you need numbers of unlimited size, such as Python's int, Java's BigInteger or JavaScript's BigInt.