Project Euler #1 test extension

Question

The simple solution to problem 1 is

static unsigned int solutionInefficient(unsigned int n){
    unsigned int sum = 0;
    for (unsigned int i = 0; i < n; i++){
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    return sum;
}

I decided to try a different test case with n = 2147483647 and the final result was computed in 12 seconds. So, I came up with another solution that gave me the same answer and took 2 seconds:

static unsigned int solutionEfficient(unsigned int n){
    unsigned int sum = 0;
    unsigned int sum3 = 0;
    unsigned int sum5 = 0;
    unsigned int sum15 = 0;
    for (unsigned int i = 3; i < n; i += 3){
        sum3 += i;
    }

    for (unsigned int i = 5; i < n; i += 5){
        sum5 += i;
    }
    for (unsigned int i = 15; i < n; i += 15){
        sum15 += i;
    }
    return sum3 + sum5 - sum15;
}

My last attempt at making a faster implementation involved some google searches and using the arithmetic summation formula and the final piece of code looked like this:

static unsigned int solutionSuperEfficient(unsigned int n){
    n = n - 1;
    unsigned int t3 = n / (unsigned int)3,
        t5 = n / (unsigned int)5,
        t15 = n / (unsigned int)15;
    unsigned int res_3 = 3 * (t3 * (t3 + 1)) *0.5;
    unsigned int res_5 = 5 * (t5 * (t5 + 1)) *0.5;
    unsigned int res_15 = 15 * (t15 * (t15 + 1)) *0.5;

    return res_3 + res_5 - res_15;
}

however this did not provide the correct answer for this test case. It did provide the correct answer for n = 1000. I am not sure why it failed for my test case, any ideas?

@avakar, you mean [UINT_MAX](http://stackoverflow.com/questions/14899088/uint-max-1-equals-what) — Fredrick Gauss, Sep 29 '15 at 05:48

score 3 · Accepted Answer · edited Sep 29 '15 at 15:35

You have two problems in your super efficient solution:

You are using floating point number 0.5 instead of dividing by 2. This will cause rounding errors. Note that it is guaranteed that x * (x + 1) is even so you can safely divide by two.
Integer overflow. The calculation t3 * (t3 + 1) and the similar products will overflow unsigned int. To avoid this, use unsigned long long instead.

Here is the corrected code:

static unsigned int solutionSuperEfficient(unsigned int n){
    n = n - 1;
    unsigned long long t3 = n / 3,
        t5 = n / 5,
        t15 = n / 15;
    unsigned long long res_3 = 3ULL * ((t3 * (t3 + 1)) / 2ULL);
    unsigned long long res_5 = 5ULL * ((t5 * (t5 + 1))  / 2ULL);
    unsigned long long res_15 = 15LL * ((t15 * (t15 + 1)) / 2ULL);

    return (unsigned int)(res_3 + res_5 - res_15);
}

In fact you don't need t3, t5 and t15 to be unsigned long long as those values would never overflow unsigned int.

Project Euler #1 test extension

1 Answers1