The square of the sum vs. the sum of the squares
The sixth Project Euler problem poses an exercise that, to me, offers no major hurdles:
What is the difference between the sum of the squares and the square of the sums [of a sequence of natural numbers]?
The functional C# solution is fairly easy to write and read:
1 public int SquareSumsLessSumSquares(IEnumerable<int> sequence)
2 {
3 var sum = sequence.Sum();
4 var sumSquares = sequence.Select(i => i * i).Sum();
5 return sum * sum - sumSquares;
6 }
We get any sequence of integers (list, array, etc.) and we find the sum of its elements at line 3. The Select() in line 4 generates a new sequence with the square of each item from the original sequence and then we add them up. From there, getting the answer to Problem 6 is easy. Actually, the specific value that the problem asks for is to find out this difference for the first 100 natural numbers, so the corresponding call is:
var result006 = SquareSumsLessSumSquares(Enumerable.Range(1, 100));
Now, given that the sequence we are focused on is 1, 2, 3, ..., 100, we can leverage a couple of math formulas:
y
Isn't the Wikipedia something? With this information in our hands we can re-write our solution this way:
1 public int SquareSumsLessSumSquaresFirstNumbers(int n)
2 {
3 var sum = n * (n + 1) / 2;
4 var sumSquares = n * (n + 1) * (2 * n + 1) / 6;
5 return sum * sum - sumSquares;
6 }
Clearly this latter way of solving the problem uses far less memory and CPU time. My first solution follows what is called a "brute force" approach, contemption intended. It works, for sure, but there are more elegant and efficient ways of solving the problem. The moral of this story is that a little research can take us a long way towards fresh solutions, probably better than our first approach. How frequently have you seen brute force solutions in production environments?