Factorial
Algorithm · Starter
Step through it: Number Theory pattern
Step 1 of 5
Goal: the greatest common divisor of 48 and 18. Key fact: the answer stays the same if you replace (a, b) with (b, the remainder of a ÷ b). The numbers shrink quickly.
Step 2 of 5
48 ÷ 18 leaves remainder 12, so carry on with (18, 12).
Step 3 of 5
18 ÷ 12 leaves 6: carry on with (12, 6).
Step 4 of 5
12 ÷ 6 leaves 0, so stop: the answer is 6. Remainders shrink fast, so only a few steps (O(log n)). The least common multiple follows: lcm = a × b ÷ gcd. These are number theory tools.
Step 5 of 5
Your turn.
In mathematics, the factorial of a non-negative integer n,
denoted by n!, is the product of all positive integers less
than or equal to n. For example:
5! = 5 * 4 * 3 * 2 * 1 = 120| n | n! |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 7 | 5 040 |
| 8 | 40 320 |
| 9 | 362 880 |
| 10 | 3 628 800 |
| 11 | 39 916 800 |
| 12 | 479 001 600 |
| 13 | 6 227 020 800 |
| 14 | 87 178 291 200 |
| 15 | 1 307 674 368 000 |
Code
/**
* @param {number} number
* @return {number}
*/
export default function factorial(number) {
let result = 1;
for (let i = 2; i <= number; i += 1) {
result *= i;
}
return result;
}/**
* @param {number} number
* @return {number}
*/
export default function factorialRecursive(number) {
return number > 1 ? number * factorialRecursive(number - 1) : 1;
}References
Practice
Number Theory
- Greatest Common Divisor of StringsEasy
- Ugly NumberEasy
- Happy NumberEasy
- Plus OneEasy
- Add BinaryEasy
- Excel Sheet Column NumberEasy
- Count PrimesMedium
- Pow(x, n)Medium
- Factorial Trailing ZeroesMedium
- Ugly Number IIMedium
- Multiply StringsMedium
- Divide Two IntegersMedium
- Water and Jug ProblemMedium
- Super PowMedium
- Largest Component Size by Common FactorHard
Spotted a mistake or something unclear? Report it on GitHub.