Grind Report 7

Problem 6

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

*WARNING: This contains the solution!*

I feel like this was a repeat of one of the previous problems. Brute force solution was obvious but I wanted to try to get something better than O(n). I wrote some stuff out but didn't come up with anything ground breaking so I just went ahead and did the brute force for the sum of the squares. The square of the sum was a repeat from a previous problem ((n * (1 + n)) / 2)^2.

Here is the very simple brute force.

#include <iostream>
using namespace std;

const int MAX = 100;

int main()
{
 int sumofsquare = 0;
 for (int i = 1; i <= MAX; ++i)
  sumofsquare += i * i;
 int squareofsum = (MAX * (1 + MAX)) / 2;
 squareofsum *= squareofsum;
 int answer = squareofsum - sumofsquare;
 cout << "Answer: " << answer << endl;
}

After solving this and gaining access to the forums I saw a great post.

(1 + 2 + ... + n)^2 = n^2 * (n+1)^2 * 1/4

1^2 + 2^2 + ... + n^2 = n * (n+1) * (2n+1) * 1/6

Very cool! I would have not been able to come up with that. The guy did not provide a proof so I am not sure how he got those numbers but they certainly work! There is the O(1) I wanted ^^