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

1

^{2}+ 2^{2}+ ... + 10^{2}= 385The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)

^{2}= 55^{2}= 3025Hence 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>After solving this and gaining access to the forums I saw a great post.

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;

}

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

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

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 ^^

## No comments:

## Post a Comment