Project Euler/13

The problem

This problem asks us to work out the first ten digits of the sum of a sequence of one-hundred 50-digit numbers.

The solution

Data structure

To do this problem I used a sequence of queues to examine these numbers one column at a time. Each 50-digit number was loaded into a char queue, and to examine the left-most digit, I popped each char and converted it to a number, then processed the running sum.

Algorithm

We know that if we have 100 numbers, the maximum of any given column is 900, which means the sum of digits in any given column can only affect two columns over, at most. For example, if I were to change all the digits in the ones place, that would change the ones place, the tens place, and possibly the hundreds place of the sum, but it will never affect the thousands place of the sum.

This gives us the information we need - to compute 1 digit of the answer, we sum up all of the leading digits, and we know that whatever is in the next column can never affect more than two columns over, so if we sum all the digits in the first column, the third place of that sum will be the first digit of the sum of all of those numbers. From there we can keep moving over, until we've generated 10 digits - then we keep moving over two more columns, since we know that a given column can be affected by the next two columns.