Problem Analysis
The task is to compute the sum of the decimal digits of 100!. The
factorial
of n is the product of all positive integers up to n, and the wrinkle is
purely one of scale: 100! has 158 decimal digits, which vastly exceeds the roughly 19
digits a 64-bit integer can hold. The problem is therefore an exercise in
arbitrary-precision arithmetic —
computation on numbers larger than a native machine word, where the value is spread across many
storage cells rather than held in a single register.
The observation that makes this tractable is that we never need n! as an abstract
number — we only ever need its decimal digits. That reframes the work as two routine sub-tasks:
repeatedly multiply a large number by a small integer (at most 100), then add up the resulting
digits. Multiplying a D-digit number by a small scalar is ordinary
long multiplication —
walk each digit, multiply, propagate a carry — an O(D) pass. Doing this for every
factor from 2 to n gives O(n · D(n)), where D(n) is the digit
count of n!. By
Stirling's approximation
D(n) grows as O(n log n), so the whole algorithm is about
O(n² log n) — utterly negligible at n = 100.
Solution Approach
Big-Integer Digit Array (C) and Built-in Arbitrary Precision (Python)
Both solutions (index 0) implement the same logical algorithm — form n!, then sum its
decimal digits — but they diverge entirely in how they represent the large number.
The C solution builds the big integer by hand. I store n! as a
little-endian
array of single decimal digits: digits[0] is the least significant digit,
digits[1] the next, and so on. I chose
little-endian
ordering deliberately, because carry propagation runs from least significant to most significant —
the same direction as increasing array index — so the inner loop always walks forward. Starting
from 1, I multiply by each i from 2 to n using
long multiplication:
for each i I walk every occupied digit, compute digits[j] * i + carry,
store the result modulo 10, and carry the quotient forward; any carry remaining past the top digit
appends new positions one digit at a time. A final pass sums every digit. I sized the buffer at 512
digits, which comfortably covers the 158 digits of 100!.
The Python solution is a single expression:
sum(int(d) for d in str(math.factorial(n))). Python's int is
arbitrary-precision arithmetic
natively, so math.factorial returns the exact value with no manual digit handling; I
convert it to a string and sum the integer value of each character. The representations differ
fundamentally: the C code works in base 10 throughout, whereas CPython stores the integer in a
binary internal form and converts to a decimal string only at the end.