Grind Report 1

As I said I was going to, I began the grinding today. The first problem was pretty easy and fairly straightforward.

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

*WARNING: This contains the solution!*

The obvious way to solve this problem is to use brute force. Doing so will result in an easy answer; however, I knew there was a better way. I cannot remember the name of the mathematician who came up with this, but I remembered that the sum of a number sequence is product of the number of terms in the sequence and the sum of the first and last terms all divided by 2.

e.g.
3 + 6 + 9 + 12 = (4 * (3 + 12)) / 2 = 30

Using this all that needed to be done was find the sum of the 2 number sequences, 3 and 5 (A number sequence would be 3 + 6 + 9 + ... + 996 + 999). Also one thing to keep in mind is that with this method, unlike the brute force, you will repeat every 15th number, this is because the lowest common multiple of 3 and 5 is 15. So we must subtract the number sequence of 15.

Here is my C++ solution.

#include <iostream>
using namespace std;

const int MAX = 999;

int sumOfMultiple(int multiple)
{
    int n = (MAX / multiple);
    int last = n * multiple;
    return (n * (multiple + last)) / 2;
}

//using some number theory, O(1)
//3 + 6 + 9 + ... + 999 = (333 * (3 + 999)) / 2
void fastforce()
{
    //get the sum of the 2 multiples (2 and 5) and remove their least common multiple (15) to remove repeats
    int sum = sumOfMultiple(3) + sumOfMultiple(5) - sumOfMultiple(15);
    cout << "Fast Force: " << sum << endl;
}

//just plow right through O(n), n = 999
void bruteforce()
{
    int sum = 0;
    for (int i = 0; i <= MAX; ++i)
    {
        if (i % 3 == 0 || i % 5 == 0)
            sum += i;
    }
    cout << "Brute Force: " << sum << endl;
}


int main()
{
    bruteforce();
    fastforce();

    return 0;
}