Project Euler #13: Large Sum

Description:


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

...

Of course I didn't include the numbers in the description...

I am sure there is a better way to do this. I just did a simple solution, where I add all the numbers and take the first 10 digits.

```
import java.math.BigInteger;

public class ProjectEuler13 {

public static void main(String[] args) {
String[] numbers = { "37107287533902102798797998220837590246510135740250",
"46376937677490009712648124896970078050417018260538",
"74324986199524741059474233309513058123726617309629",
"91942213363574161572522430563301811072406154908250",
"23067588207539346171171980310421047513778063246676",
"89261670696623633820136378418383684178734361726757",
"28112879812849979408065481931592621691275889832738",
"44274228917432520321923589422876796487670272189318",
"47451445736001306439091167216856844588711603153276",
"70386486105843025439939619828917593665686757934951",
"62176457141856560629502157223196586755079324193331",
"64906352462741904929101432445813822663347944758178",
"92575867718337217661963751590579239728245598838407",
"58203565325359399008402633568948830189458628227828",
"80181199384826282014278194139940567587151170094390",
"35398664372827112653829987240784473053190104293586",
"86515506006295864861532075273371959191420517255829",
"71693888707715466499115593487603532921714970056938",
"54370070576826684624621495650076471787294438377604",
"53282654108756828443191190634694037855217779295145",
"36123272525000296071075082563815656710885258350721",
"45876576172410976447339110607218265236877223636045",
"174237069058

Update

See the comments for corner cases.

Original

When I solved this problem, I readily noticed what the problem expected the programmers to understand. Let me put it this way...

An analogy

Have you ever seen a car's odometer? If you have, you will notice that the digits in the far right increase fastest while you drive. The next digit, i.e. towards the left updates less frequently (ten times slower). The next is even slower and the left-most digit is the slowest; it doesn't update even if you drive for hours at a stretch.

Relation

What is its relation to the problem at hand? We must understand the significance of the least significant digits is to provide the "carry" to be added to the next significant digit. Let's take our analogy and proceed with it. The rightmost digits act as the miles, tens-of-miles, hundreds-of-miles counters, that update frequently. When they cross \$9\$ and return to \$0\$, they increment the immediate left digit. It is essentially updating using the carry. These carries too become lesser and lesser in frequency as we move leftwards.

For example, take \$10,950\$ and \$15,456\$. Add them up and you get \$26,406\$. We want the first two digits of their sum. If we take \$10,000\$ and \$15,000\$, we get a slightly different answer: \$25,000\$.

If we analyse the first 2 (i.e. leftmost) digits of the answers, we see that they \$25\$ and \$26\$ differ in their one's place. Their first digits match up. That's why I said "slightly".

In order to improve the precision, take an extra (buffer) digit. Using three digits: \$109+154=263\$. There you go! We now have the answers matching in their first two digits. This theory can be generalized to obtain the first \$n\$ digits of the sum of a collection of numbers (of length more than \$n\$ digits). The number of buffer digits depends on the "number of numbers" A rough relation would be

$$
No.\ of\ buffer\ digits = log(no.\ of\ items)
$$

Trial and error supports this. I urge you to prove it yourself.

The code

Finally, let's get cracking

public class ProjectEuler13 {

    public static void main(String[] args) {
        String[] numbers = {
            // The big long list
            };
        long time = System.nanoTime();
        String result = sum(numbers, 10).substring(0, 10);
        time = System.nanoTime() - time;
        System.out.println("Result: " + result + "\nTime in nanoseconds: " + time);
    }

    public static String sum(String[] values, int numberOfDigits) {
        // best to take an overestimate
        int buffer = (int) Math.ceil(Math.log10(values.length)); // = 2 for 50
        int length = numberOfDigits + buffer;
        long result = 0;
        for (String value : values) {
            result += Long.parseLong(value.substring(0, length));
        }
        return String.valueOf(result);
    }

}

Even on my slow computer:


Result: 5537376230

Time in nanoseconds: 2493350

StackExchange Code Review Q#110512, answer score: 10