Factorial of a number
Factorial of a number is a easy recursion & backtracking problem solved with the basic recursion pattern.
The best approach, iterative, runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from recursive up.
Problem
Compute n!, the product of all integers from 1 to n (with 0! = 1). This is the first problem for learning how recursion works: base case, recursive step and the call stack.
Examples
Example 1
- Input
n = 5- Output
120- Why
- 5 × 4 × 3 × 2 × 1.
Example 2
- Input
n = 0- Output
1
Constraints
0 <= n <= 20(20! still fits in a long)
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Recursive | O(n) | O(n) |
| Iterative | O(n) | O(1) |
1Recursive
O(n)O(n)n frames on the call stack.State the answer in terms of a smaller version of the same problem: fact(n) = n · fact(n - 1), with fact(0) = 1. Use it to picture the call stack: calls go down to the base case, and results are multiplied on the way back up.
- Base case: if n <= 1, return 1.
- Return n * fact(n - 1).
class Solution {
static long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
}class Solution:
def factorial(self, n: int) -> int:
if n <= 1:
return 1
return n * self.factorial(n - 1)class Solution {
public:
static long long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
};function factorial(n) {
if (n <= 1) return 1n;
return BigInt(n) * factorial(n - 1);
}2Iterative
O(n)O(1)Multiply 1 · 2 · ... · n in a loop. Same result, no call stack.
- r = 1; for i in 2..n: r *= i.
class Solution {
static long factorial(int n) {
long r = 1;
for (int i = 2; i <= n; i++) r *= i;
return r;
}
}class Solution:
def factorial(self, n: int) -> int:
r = 1
for i in range(2, n + 1):
r *= i
return rclass Solution {
public:
static long long factorial(int n) {
long long r = 1;
for (int i = 2; i <= n; i++) r *= i;
return r;
}
};function factorial(n) {
let r = 1n;
for (let i = 2; i <= n; i++) r *= BigInt(i);
return r;
}Edge cases to test
- n = 0 (base case, 0! = 1)
- Overflow beyond 20!
Hints
Hint 1
Every recursive function needs a base case that stops, and a step that moves toward it: n! = n × (n - 1)!.
FAQ
What is the best time complexity for Factorial of a number?
Iterative runs in O(n) time and O(1) extra space.
Which pattern does Factorial of a number use?
It is a recursion & backtracking problem that uses the basic recursion pattern. Other problems with the same pattern: Fibonacci Number, Binary Tree Inorder Traversal (Recursive), Basic Backtracking Template.
Is there a brute force solution for Factorial of a number?
Yes. Recursive takes O(n) time and O(n) space. State the answer in terms of a smaller version of the same problem: fact(n) = n · fact(n - 1), with fact(0) = 1.
Which edge cases should I test for Factorial of a number?
n = 0 (base case, 0! = 1); Overflow beyond 20!.