Problem Analysis
The task is to compute the exact sum of one hundred 50-digit integers and report its leading ten digits. The mathematical difficulty is purely one of magnitude: a 50-digit number is far beyond the range of a 64-bit integer, which tops out around 18 to 19 decimal digits (the maximum unsigned 64-bit value is roughly 1.8 x 10^19). Any attempt at naive machine arithmetic would overflow silently and produce garbage. The solution therefore requires arbitrary-precision arithmetic, which means working with numbers whose digit count is bounded only by available memory, not by a fixed machine word size.
The key observation that keeps this cheap is about how addition propagates information. In base 10
addition, a carry
only ever moves from a less-significant digit toward a more-significant one - never the reverse.
This means the high-order digits of the result depend only on the high-order digits of the inputs
plus whatever carry
bubbles up from below. Summing 100 numbers can generate a
carry
of at most about log10(100) = 2 extra digit positions into the leading region. So if I
only need the first 10 digits, I do not have to carry all 50 digits to full precision: keeping a
small number of guard digits beyond the ten I want is enough to capture every
carry
that could influence the answer. The asymptotic complexity is O(N x D), where N = 100 is the count
of numbers and D is the number of digits processed per number. For this fixed input that is
effectively constant work, and both implementations run in indistinguishable-from-zero time.
Solution Approach
Algorithm 0 - Prefix Truncation with Big-Integer or Manual Digit Addition
Both the Python and C solutions share one strategy: rather than summing the full 50-digit numbers
and slicing the prefix off the end, they truncate each operand to its first digits + 1
characters before summing. That single extra digit is the guard digit - it absorbs any
carry
that would otherwise have crept up from the discarded lower positions. The result is then trimmed to
the requested number of leading digits.
The Python version leans entirely on the language's native
arbitrary-precision integers.
Each line of the multiline data string is sliced with i[: digits + 1], converted with
int(), and fed into sum():
str(sum([int(i[: digits + 1]) for i in numbers.splitlines() if i != ""]))[:digits].
Because Python's int grows to whatever size it needs, the addition is exact and there
is no overflow to reason about. The splitlines() call separates the embedded data into
individual number strings and the if i != "" guard discards the empty trailing line.
For the larger test cases (20 and 100 digits) the same code path works without modification - when
digits + 1 exceeds 50 the slice simply returns the whole number.
The C version has no built-in big integer, so it makes the digit mechanics explicit. I maintain an
accumulator array acc[] of length use_digits + 4, where
use_digits = min(digits + 1, 50). The four extra cells give headroom for the
carries
produced by summing 100 numbers. The algorithm proceeds in two passes. First, an accumulation pass
adds each input digit (converted from ASCII with numbers[n][d] - '0') into its
column of the accumulator, right-aligned. Each accumulator cell can therefore reach at most
9 x 100 = 900, comfortably within the range of an int, so I need not
normalize after every addition. Second, a pass that propagates the
carries
sweeps right to left, pushing acc[i] / 10 into the cell to the left and leaving
acc[i] % 10 behind. Finally I skip leading zeros, copy the first digits
significant digits into a freshly malloc'd buffer, and return it to the caller, which
is responsible for freeing it.
The two implementations are algorithmically identical; the only difference is who manages the big-integer representation. Python delegates it to the runtime; C does it by hand with a digit array. Both pass all three test cases with identical answers.