100 Factorial – Tech Interview Dot Org

how many trailing zeroes are there in 100! (100 factorial)?

Solution

One per factor of 10, and one per factor of 5 (there are more than enough 2’s to pair with the 5’s), plus one per factor of ten squared (one occurrence) and one per factor of 5 squared (three occurrences).

So if I’m counting correctly, that’d be 10 + 10 + 1 + 3== 24 zeroes.

Assuming the question meant *trailing* zeroes. It’d be much harder to also count the intermingled zero digits in the entire expansion.

💡Strategies for Solving This Problem

Recursion and Large Numbers

This showed up at Amazon in 2024. Seems simple but tests recursion, overflow handling, and optimization thinking.

The Problem

Calculate 100! (100 factorial). That's 100 × 99 × 98 × ... × 2 × 1.

Challenge: Result has 158 digits. Standard integers overflow. Need BigInt or custom solution.

Approach 1: Simple Recursion

Classic factorial:

factorial(n) = n × factorial(n-1)
factorial(0) = 1

O(n) time, O(n) space for call stack. Works but not optimized.

Approach 2: Iterative

Loop from 1 to n, multiply. Same O(n) time but O(1) space. Better.

Approach 3: Tail Recursion

Convert to tail-recursive form so compiler can optimize to iteration. Some languages (not JavaScript) optimize this automatically.

The Real Challenge: BigInt

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

That's 158 digits. Need arbitrary precision arithmetic.

JavaScript has BigInt built-in (ES2020+). Other languages need libraries or manual implementation.

Optimization: Memoization

If calculating multiple factorials, cache results. factorial(100) uses factorial(99), etc.

At Amazon

Started with simple recursion. Interviewer asked "What about overflow?" That's when I switched to BigInt. Then asked "How to optimize for many queries?" Showed memoization.

Also discussed: How many trailing zeros? (24 - count factors of 5)

✅Solution

Solution: Iterative with BigInt

function factorial(n) {
    if (n < 0) return undefined;
    if (n === 0 || n === 1) return 1n;  // BigInt literal

    let result = 1n;
    for (let i = 2n; i <= BigInt(n); i++) {
        result *= i;
    }

    return result;
}

// Test
console.log(factorial(100).toString());
// 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

console.log(factorial(10));   // 3628800n
console.log(factorial(20));   // 2432902008176640000n
console.log(factorial(0));    // 1n

Recursive Solution

function factorialRecursive(n) {
    if (n < 0) return undefined;
    if (n === 0 || n === 1) return 1n;

    return BigInt(n) * factorialRecursive(n - 1);
}

console.log(factorialRecursive(100).toString());

Tail Recursive (Optimizable)

function factorialTail(n, accumulator = 1n) {
    if (n < 0) return undefined;
    if (n === 0 || n === 1) return accumulator;

    return factorialTail(n - 1, BigInt(n) * accumulator);
}

console.log(factorialTail(100).toString());

With Memoization

const factorialMemo = (() => {
    const cache = new Map();
    cache.set(0, 1n);
    cache.set(1, 1n);

    return function factorial(n) {
        if (n < 0) return undefined;

        if (cache.has(n)) {
            return cache.get(n);
        }

        const result = BigInt(n) * factorial(n - 1);
        cache.set(n, result);
        return result;
    };
})();

// Much faster for repeated calls
console.log(factorialMemo(100).toString());
console.log(factorialMemo(99).toString());  // Instant (cached)
console.log(factorialMemo(101).toString()); // Only 1 multiply needed

Count Digits

function countDigits(n) {
    return factorial(n).toString().length;
}

console.log(countDigits(100));  // 158 digits
console.log(countDigits(1000)); // 2568 digits

Count Trailing Zeros

function trailingZeros(n) {
    // Trailing zeros come from factors of 10 = 2 × 5
    // There are always more 2s than 5s, so count 5s

    let count = 0;
    let powerOf5 = 5;

    while (powerOf5 <= n) {
        count += Math.floor(n / powerOf5);
        powerOf5 *= 5;
    }

    return count;
}

console.log(trailingZeros(100));  // 24
console.log(trailingZeros(1000)); // 249

// Verify
const fact100 = factorial(100).toString();
console.log("100! ends with:", fact100.slice(-30));
// Shows 24 zeros at end

Without BigInt (Manual Implementation)

function factorialManual(n) {
    if (n < 0) return undefined;
    if (n === 0 || n === 1) return "1";

    // Represent number as array of digits
    let result = [1];

    for (let num = 2; num <= n; num++) {
        let carry = 0;

        for (let i = 0; i < result.length; i++) {
            const prod = result[i] * num + carry;
            result[i] = prod % 10;
            carry = Math.floor(prod / 10);
        }

        while (carry > 0) {
            result.push(carry % 10);
            carry = Math.floor(carry / 10);
        }
    }

    return result.reverse().join('');
}

console.log(factorialManual(100));

Complexity Analysis

Approach	Time	Space
Iterative	O(n)	O(1)*
Recursive	O(n)	O(n)
Tail recursive	O(n)	O(1)**
Memoized	O(n) first call, O(1) cached	O(n)

* Not counting BigInt storage
** If compiler optimizes tail calls

Why 100! Has 158 Digits?

Using Stirling's approximation:

log₁₀(n!) ≈ n × log₁₀(n) - n × log₁₀(e) + 0.5 × log₁₀(2πn)

For n=100:
log₁₀(100!) ≈ 157.97
So 100! ≈ 10^157.97

Number of digits = floor(157.97) + 1 = 158

Common Mistakes

Integer overflow: Using regular numbers for large n
Stack overflow: Deep recursion without tail call optimization
Negative input: Not handling n < 0 (undefined for factorials)
Mixing types: Forgetting BigInt suffix (n) or BigInt() conversion

Follow-Up Questions

Q: How to calculate nCr (combinations)?
A: nCr = n! / (r! × (n-r)!), but better to cancel terms to avoid overflow

Q: What about double factorial (n!!)?
A: Multiply every other number: n × (n-2) × (n-4) × ...

Q: Gamma function?
A: Γ(n) = (n-1)! extends factorials to non-integers