notes.html

problem 13 · 73 lines

<article>
<h3>Problem Analysis</h3>
<p>
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
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a>,
which means working with numbers whose digit count is bounded only by available memory, not by a
fixed machine word size.
</p>
<p>
The key observation that keeps this cheap is about how addition propagates information. In base 10
addition, a <a class="reference-source" href="https://en.wikipedia.org/wiki/Carry_(arithmetic)" rel="noopener noreferrer" target="_blank">carry</a>
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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Carry_(arithmetic)" rel="noopener noreferrer" target="_blank">carry</a>
bubbles up from below. Summing 100 numbers can generate a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Carry_(arithmetic)" rel="noopener noreferrer" target="_blank">carry</a>
of at most about <code>log10(100) = 2</code> 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
<a class="reference-source" href="https://en.wikipedia.org/wiki/Carry_(arithmetic)" rel="noopener noreferrer" target="_blank">carry</a>
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.
</p>
<h3>Solution Approach</h3>
<h4>Algorithm 0 - Prefix Truncation with Big-Integer or Manual Digit Addition</h4>
<p>
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 <code>digits + 1</code>
characters before summing. That single extra digit is the guard digit - it absorbs any
<a class="reference-source" href="https://en.wikipedia.org/wiki/Carry_(arithmetic)" rel="noopener noreferrer" target="_blank">carry</a>
that would otherwise have crept up from the discarded lower positions. The result is then trimmed to
the requested number of leading digits.
</p>
<p>
The Python version leans entirely on the language's native
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision integers</a>.
Each line of the multiline data string is sliced with <code>i[: digits + 1]</code>, converted with
<code>int()</code>, and fed into <code>sum()</code>:
<code>str(sum([int(i[: digits + 1]) for i in numbers.splitlines() if i != ""]))[:digits]</code>.
Because Python's <code>int</code> grows to whatever size it needs, the addition is exact and there
is no overflow to reason about. The <code>splitlines()</code> call separates the embedded data into
individual number strings and the <code>if i != ""</code> guard discards the empty trailing line.
For the larger test cases (20 and 100 digits) the same code path works without modification - when
<code>digits + 1</code> exceeds 50 the slice simply returns the whole number.
</p>
<p>
The C version has no built-in big integer, so it makes the digit mechanics explicit. I maintain an
accumulator array <code>acc[]</code> of length <code>use_digits + 4</code>, where
<code>use_digits = min(digits + 1, 50)</code>. The four extra cells give headroom for the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Carry_(arithmetic)" rel="noopener noreferrer" target="_blank">carries</a>
produced by summing 100 numbers. The algorithm proceeds in two passes. First, an accumulation pass
adds each input digit (converted from ASCII with <code>numbers[n][d] - '0'</code>) into its
column of the accumulator, right-aligned. Each accumulator cell can therefore reach at most
<code>9 x 100 = 900</code>, comfortably within the range of an <code>int</code>, so I need not
normalize after every addition. Second, a pass that propagates the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Carry_(arithmetic)" rel="noopener noreferrer" target="_blank">carries</a>
sweeps right to left, pushing <code>acc[i] / 10</code> into the cell to the left and leaving
<code>acc[i] % 10</code> behind. Finally I skip leading zeros, copy the first <code>digits</code>
significant digits into a freshly <code>malloc</code>'d buffer, and return it to the caller, which
is responsible for freeing it.
</p>
<p>
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.
</p>
</article>