Factorial of a large number

Easy

Problem

Given n (up to about 1000), return n! as a string or digit array. The result has far more digits than any built-in number type can hold, so you must do the arithmetic digit by digit.

Example 1

Input:  n = 5
Output: 120

Example 2

Input:  n = 25
Output: 15511210043330985984000000

Also asked as: Find factorial of a large number

Test cases

Case 1

Input:    5
Expected: "120"

Case 2

Input:    25
Expected: "15511210043330985984000000"

Case 3

Input:    10
Expected: "3628800"

Case 4

Input:    0
Expected: "1"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Digit array multiplication

Time O(n · digits)Space O(digits)

Store the result least-significant-digit first; multiply the whole array by each k from 2..n, propagating carry.

function factorial(n) {
let digits = [1];
for (let k = 2; k <= n; k++) {
let carry = 0;
for (let i = 0; i < digits.length; i++) {
const prod = digits[i] * k + carry;
digits[i] = prod % 10;
carry = Math.floor(prod / 10);
}
while (carry) { digits.push(carry % 10); carry = Math.floor(carry / 10); }
}
return digits.reverse().join('');
}

In modern JS you can also just use BigInt: let f = 1n; for (let i = 2n; i <= BigInt(n); i++) f *= i;