Project Euler Problem 13

Large Sum

Project Euler presents the following Problem #13:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

$$37107287533902102798797998220837590246510135740250\\ 46376937677490009712648124896970078050417018260538\\ 74324986199524741059474233309513058123726617309629\\ 91942213363574161572522430563301811072406154908250\\ 23067588207539346171171980310421047513778063246676\\ 89261670696623633820136378418383684178734361726757\\ 28112879812849979408065481931592621691275889832738\\ 44274228917432520321923589422876796487670272189318\\ 47451445736001306439091167216856844588711603153276\\ 70386486105843025439939619828917593665686757934951\\ 62176457141856560629502157223196586755079324193331\\ 64906352462741904929101432445813822663347944758178\\ 92575867718337217661963751590579239728245598838407\\ 58203565325359399008402633568948830189458628227828\\ 80181199384826282014278194139940567587151170094390\\ 35398664372827112653829987240784473053190104293586\\ 86515506006295864861532075273371959191420517255829\\ 71693888707715466499115593487603532921714970056938\\ 54370070576826684624621495650076471787294438377604\\ 53282654108756828443191190634694037855217779295145\\ 36123272525000296071075082563815656710885258350721\\ 45876576172410976447339110607218265236877223636045\\ 17423706905851860660448207621209813287860733969412\\ 81142660418086830619328460811191061556940512689692\\ 51934325451728388641918047049293215058642563049483\\ 62467221648435076201727918039944693004732956340691\\ 15732444386908125794514089057706229429197107928209\\ 55037687525678773091862540744969844508330393682126\\ 18336384825330154686196124348767681297534375946515\\ 80386287592878490201521685554828717201219257766954\\ 78182833757993103614740356856449095527097864797581\\ 16726320100436897842553539920931837441497806860984\\ 48403098129077791799088218795327364475675590848030\\ 87086987551392711854517078544161852424320693150332\\ 59959406895756536782107074926966537676326235447210\\ 69793950679652694742597709739166693763042633987085\\ 41052684708299085211399427365734116182760315001271\\ 65378607361501080857009149939512557028198746004375\\ 35829035317434717326932123578154982629742552737307\\ 94953759765105305946966067683156574377167401875275\\ 88902802571733229619176668713819931811048770190271\\ 25267680276078003013678680992525463401061632866526\\ 36270218540497705585629946580636237993140746255962\\ 24074486908231174977792365466257246923322810917141\\ 91430288197103288597806669760892938638285025333403\\ 34413065578016127815921815005561868836468420090470\\ 23053081172816430487623791969842487255036638784583\\ 11487696932154902810424020138335124462181441773470\\ 63783299490636259666498587618221225225512486764533\\ 67720186971698544312419572409913959008952310058822\\ 95548255300263520781532296796249481641953868218774\\ 76085327132285723110424803456124867697064507995236\\ 37774242535411291684276865538926205024910326572967\\ 23701913275725675285653248258265463092207058596522\\ 29798860272258331913126375147341994889534765745501\\ 18495701454879288984856827726077713721403798879715\\ 38298203783031473527721580348144513491373226651381\\ 34829543829199918180278916522431027392251122869539\\ 40957953066405232632538044100059654939159879593635\\ 29746152185502371307642255121183693803580388584903\\ 41698116222072977186158236678424689157993532961922\\ 62467957194401269043877107275048102390895523597457\\ 23189706772547915061505504953922979530901129967519\\ 86188088225875314529584099251203829009407770775672\\ 11306739708304724483816533873502340845647058077308\\ 82959174767140363198008187129011875491310547126581\\ 97623331044818386269515456334926366572897563400500\\ 42846280183517070527831839425882145521227251250327\\ 55121603546981200581762165212827652751691296897789\\ 32238195734329339946437501907836945765883352399886\\ 75506164965184775180738168837861091527357929701337\\ 62177842752192623401942399639168044983993173312731\\ 32924185707147349566916674687634660915035914677504\\ 99518671430235219628894890102423325116913619626622\\ 73267460800591547471830798392868535206946944540724\\ 76841822524674417161514036427982273348055556214818\\ 97142617910342598647204516893989422179826088076852\\ 87783646182799346313767754307809363333018982642090\\ 10848802521674670883215120185883543223812876952786\\ 71329612474782464538636993009049310363619763878039\\ 62184073572399794223406235393808339651327408011116\\ 66627891981488087797941876876144230030984490851411\\ 60661826293682836764744779239180335110989069790714\\ 85786944089552990653640447425576083659976645795096\\ 66024396409905389607120198219976047599490197230297\\ 64913982680032973156037120041377903785566085089252\\ 16730939319872750275468906903707539413042652315011\\ 94809377245048795150954100921645863754710598436791\\ 78639167021187492431995700641917969777599028300699\\ 15368713711936614952811305876380278410754449733078\\ 40789923115535562561142322423255033685442488917353\\ 44889911501440648020369068063960672322193204149535\\ 41503128880339536053299340368006977710650566631954\\ 81234880673210146739058568557934581403627822703280\\ 82616570773948327592232845941706525094512325230608\\ 22918802058777319719839450180888072429661980811197\\ 77158542502016545090413245809786882778948721859617\\ 72107838435069186155435662884062257473692284509516\\ 20849603980134001723930671666823555245252804609722\\ 53503534226472524250874054075591789781264330331690$$

❤️ Problem #13 is by far one of my favorite Project Euler problems to revisit. The official site ranks it as the 14th easiest problem at the time of writing, but even a less challenging problem can be memorable when it highlights the intricacies of different programming languages. We'll consider solutions in Kotlin, Python, and C++, as well as a more language-agnostic approach.

Large Number Handling

Kotlin

Kotlin's largest built-in numeric type, Long, represents a 64-bit signed integer and is far too small to hold this problem's 50-digit numbers. The largest supported integer, Long.MAX_VALUE, is only equal to a 19-digit number, 9_223_372_036_854_775_807.

Regardless, Kotlin's interoperability with Java means it has access to arbitrary-precision integers through the BigInteger class, which allows us to easily solve this problem with a single import statement:

1import java.math.BigInteger
2
3fun sliceSum(numbers: List<String>): String {
4    return numbers.sumOf { BigInteger(it) }.toString().take(10)
5}

The BigInteger class is a useful tool to become quickly familiar with as it provides assistance for large number modular arithmetic operations and primality testing in several future Project Euler problems. While not proven to be a constraint in the first hundred problems, it must still be mentioned that the class does have its set limits:

... BigInteger constructors and operations throw ArithmeticException when the result is out of the supported range of $-2^\text{Integer.MAX\_VALUE}$ (exclusive) to $+2^\text{Integer.MAX\_VALUE}$ (exclusive).

Python

Python takes this problem and eats it like a piece of 🍰. As of Python 3, the language's only intrinsic numeric types are: integer, floating point number, and complex number, with the int type having no precision restriction. Handling 50-digit numbers is therefore as simple as reading, casting, and adding them, no import statement necessary:

1def slice_sum(numbers: list[str]) -> str:
2    return str(sum(map(int, numbers)))[:10]

C++

C++ numeric types include unsigned long long int, which represents a 64-bit unsigned integer with a 20-digit maximum of 18_446_744_073_709_551_615. For more precision, the boost multiprecision library does exist with various data type options.

As a learning opportunity, this problem became the motivation to implement my own custom BigInteger class tailored to the specific needs of this and future problems. Starting with the very minimum, Problem #13 only requires the implementation of constructors, a cast-to-string function, and the addition operator (as well as the addition assignment operator, based on design choice).

This custom class is then used with std::accumulate() from the numeric library and a binary operation function to sum up the input strings, in a manner similar to the previous two languages:

1#include <numeric>
2
3#include "pe-custom/big-int.h"
4
5std::string sliceSum(const std::vector<std::string>& numbers)
6{
7    return std::accumulate(
8            numbers.cbegin(),
9            numbers.cend(),
10            BigInt::zero(),
11            [](BigInt& acc, std::string num) {
12                return acc + BigInt {num};
13            })
14            .toString()
15            .substr(0, 10);
16}

🤔 So we've found a solution in three different languages, but why stop there when we can find common ground?

Manual Addition

It is entirely possible to solve this problem using only the input strings by simulating the right-to-left technique one (potentially) uses when adding numbers manually. That is, each rightmost digit of each input string is summed and the rightmost digit of the result is stored, with the result divided by 10 pushed to a carry-over value. The cycle continues with a shift to the left and the new sum this time including the carry-over value.

In such a solution, the resulting output is stored as a string that is processed with each iteration to maintain the desired length of ten digits. The final output is returned as a reversed string:

1fun addInReverse(numbers: List<String>): String {
2    val n = numbers.size
3    if (n == 1) return numbers.single().slice(0..9)
4    
5    var output = ""
6    var carryOver = 0
7    for (i in 49 downTo 0) {
8        val sum = numbers.sumOf { it[i].digitToInt() } + carryOver
9        output = (if (output.length == 10) output.drop(1) else output) + sum % 10
10        carryOver = sum / 10
11    }
12    
13    while (carryOver > 0) {
14        output = (if (output.length == 10) output.drop(1) else output) + carryOver % 10
15        carryOver /= 10
16    }
17    return output.reversed()
18}

Line 13: This accounts for any potential overflow remaining in carryOver after all the digits have been added.

This solution can be tailored heavily to fit personal preference. For example, the input strings could be read in reverse if it feels more natural to visualize the inner for loop moving left-to-right. The output could also be stored as a single growing unprocessed string, thereby removing the repeated conditional checks, with takeLast(10).reversed() chained to the final string.

Personally, the thought of repeatedly creating and processing new strings as dynamic storage was unappealing, so I originally wrote a different version that used a small class meant to mimic a bounded circular buffer. Using this mechanism abstracts away the data storage logic, so that new digits can be added without worrying about how they are being handled. My version inherits from Java's ArrayBlockingQueue class and overrides a single function:

1import java.util.concurrent.ArrayBlockingQueue
2
3class RollingQueue<E>(
4    capacity: Int
5) : ArrayBlockingQueue<E>(capacity) {
6    /**
7     * Inserts an element at the tail of the queue without exceeding capacity, 
8     * by auto-removing the head if full.
9     *
10     * The original method would block this action if the queue was full by 
11     * throwing an IllegalStateException.
12     *
13     * @return true, always.
14     */
15    override fun add(element: E): Boolean {
16        return if (offer(element)) {
17            true
18        } else {
19            poll()
20            offer(element)
21        }
22    }
23}

📍 A circular buffer only proves to be useful in two out of the first hundred Project Euler problems, so this tiny subclass currently suffices, but maybe future problems will warrant the implementation of a fully custom class.

Here's the original addInReverse(), which uses RollingQueue to store the final output:

1import util.custom.RollingQueue
2
3fun addInReverse(numbers: List<String>): String {
4    val n = numbers.size
5    if (n == 1) return numbers.single().slice(0..9)
6    
7    val output = RollingQueue<Int>(10)
8    var carryOver = 0
9    for (i in 49 downTo 0) {
10        val sum = numbers.sumOf { it[i].digitToInt() } + carryOver
11        output.add(sum % 10)
12        carryOver = sum / 10
13    }
14    
15    while (carryOver > 0) {
16        output.add(carryOver % 10)
17        carryOver /= 10
18    }
19    return output.reversed().joinToString("")
20}

Speed Comparison

Here are the average execution speeds for the three Kotlin solutions mentioned above, using two test resources of $N$ 50-digit numbers:

Visit the following links to see the Kotlin, Python, and C++ source code and test suites in their respective repositories:

• Kotlin source: solution tests
• Python source: solution tests
• C++ source: solution & tests

Problem content on the Project Euler site is licensed under a Creative Commons (CC) License: CC BY-NC-SA 4.0. Solutions to only the first hundred problems are encouraged to be distributed publicly.

Thanks for reading!🏝️➕☕🐍⚡