22. Find Factorial of a Large Number

Given n, compute n! exactly, even when it's too large to fit in a standard 64-bit integer. Print the exact value.

Input: The input is a single line containing the integer n. Output: Print the exact value of n!, with no truncation.

0 <= n <= 100

This 'store as a digit array and do manual carrying arithmetic' technique is the same core idea behind any 'big number' arithmetic problem - once you've built it for multiplication here, the same representation extends to big-number addition, subtraction, and beyond.

Compute n factorial (n! = n × (n-1) × ... × 1) exactly, even when the result is far too big to fit in a normal number type. Brute force: Use a standard 64-bit integer type directly and multiply normally - this works fine for small n, but for n as large as 100, the true factorial has over 150 digits, far exceeding what ANY fixed-size integer type (even 64-bit) can represent, causing silent overflow and an incorrect answer. Optimised: Representing the number as an array/list of individual digits (or using a language's arbitrary-precision integer type, if available) sidesteps the fixed-size overflow problem entirely - multiplication is performed digit-by-digit with explicit carrying, exactly mirroring how you'd multiply large numbers by hand on paper, so the representation can grow to however many digits are actually needed.

Instead of multiplying the (rapidly growing) running total by one small number at a time, recursively split the range [2, n] into two halves, compute the big-integer product of each half independently, and multiply the two resulting big integers together to combine them. Because this schedule always multiplies two numbers of roughly comparable size (a "balanced" multiplication) rather than repeatedly multiplying a huge accumulator by a tiny factor, it drastically reduces the total digit-operation count for large n, and can be combined with fast multiplication (e.g. Karatsuba) for an even better asymptotic bound. Time: O(n log^2 n) with fast multiplication Space: O(n log n)

Represent the growing result as an array of individual decimal digits (least significant first), initialized to [1]. For each i from 2 to n, multiply every digit in the array by i, propagating carries into higher digit positions just like doing long multiplication by hand. Since the number of digits D grows roughly proportionally to n log n (by Stirling's approximation) and each of the n multiplication steps touches every digit, the total digit-operations grow faster than linearly in n. Time: O(n^2 log n) Space: O(n log n)

Instead of storing one decimal digit per array slot, store large chunks (e.g. base 10^9, so each array slot holds up to 9 decimal digits) and multiply the whole chunk array by i at each step, propagating carries between chunks exactly as before. This keeps the same overall algorithm as the brute approach but shrinks the array length by roughly a factor of 9, meaning each of the n multiplication passes touches far fewer array elements, giving a large constant-factor speedup while remaining the same asymptotic technique. Time: O(n^2 log n / 81) Space: O(n log n / 9)

1. Represent the growing result as a list of individual digits (or use your language's built-in big-integer type if it has one). 2. Start with the result representing just the number 1. 3. Multiply this growing 'big number' by each integer from 2 up to n, one at a time, exactly like manual long multiplication with carrying. 4. After multiplying by every number up to n, the digit list represents the exact value of n factorial.

Time: Proportional to n multiplied by the NUMBER OF DIGITS in the growing result (which itself grows as n increases) - noticeably more work than simple fixed-size multiplication, but necessary to get an exact, correct answer for large n. Space: Proportional to the number of digits in the final result, which grows roughly proportionally to n log n for large n.

n = 0 (0! = 1, by definition); n = 1 (1! = 1); and n = 100 (the largest value, producing a very large number that requires a bignum or digit-array approach).

Be ready to explain WHY a normal fixed-size integer type overflows here, with a concrete sense of scale (100! has over 150 digits) - this demonstrates genuine awareness of integer overflow, a broadly important, frequently-tested concept.