by Zoran Horvat

Dec 14, 2013

Given a positive number N, write a function which returns sum of squares of numbers between 1 and N, i.e. 1^2 + 2^2 + ... + N^2.

Example: If N is 5, then return value should be 55 (1 + 4 + 9 + 16 + 25 = 55).

It is easy to produce sum o squares of a sequence by simply iterating through numbers 1 to N. Here is the function which does precisely that:

```
function Sum(n)
begin
sum = 0
for i = 1 to n
sum = sum + i * i
return sum
end
```

This function runs in O(N) time and O(1) space. In order to improve the running time of the function, we need to find a definite form of the sum of squares. That is possible to do, and here is one of the ways to derive the simple form of the expression:

This derivation depends on the equation for calculating simple sum of the numbers 1 to N, which is explained in exercise Sum of First N Numbers. Now the function that runs in O(1) time and O(1) space looks like this:

```
function Sum(n)
begin
return n * (n + 1) * (2 * n + 1) / 6
end
```

Below is the full listing of a console application in C# which lets the user enter value N and then prints the sum of squares of the sequence.

```
using System;
namespace SumOfSquares
{
public class Program
{
static int Sum(int n)
{
return n * (n + 1) * (2 * n + 1) 6;
}
static void Main(string[] args)
{
while (true)
{
Console.Write("Enter sequence length (zero to exit): ");
int n = int.Parse(Console.ReadLine());
if (n <= 0)
break;
Console.WriteLine("Sum of the sequence is {0}\n", Sum(n));
}
}
}
}
```

When application is run, it produces output like this:

```
Enter sequence length (zero to exit): 4
Sum of the sequence is 30
Enter sequence length (zero to exit): 5
Sum of the sequence is 55
Enter sequence length (zero to exit): 217
Sum of the sequence is 3429685
Enter sequence length (zero to exit): 0
```

If you wish to learn more, please watch my latest video courses

This course begins with examination of a realistic application, which is poorly factored and doesn't incorporate design patterns. It is nearly impossible to maintain and develop this application further, due to its poor structure and design.

As demonstration after demonstration will unfold, we will refactor this entire application, fitting many design patterns into place almost without effort. By the end of the course, you will know how code refactoring and design patterns can operate together, and help each other create great design.

More...

In four and a half hours of this course, you will learn how to control design of classes, design of complex algorithms, and how to recognize and implement data structures.

After completing this course, you will know how to develop a large and complex domain model, which you will be able to maintain and extend further. And, not to forget, the model you develop in this way will be correct and free of bugs.

More...

Zoran Horvat is the Principal Consultant at Coding Helmet, speaker and author of 100+ articles, and independent trainer on .NET technology stack. He can often be found speaking at conferences and user groups, promoting object-oriented development style and clean coding practices and techniques that improve longevity of complex business applications.

- Does the Command Pattern Require Undo?
- What Makes while Loop a Poor Choice in Programming
- How to Wrap System.Random Into an Infinite IEnumerable<int> Sequence
- Substituting the Builder with the Sequence of Factory Methods
- Custom Implementation of the Option/Maybe Type in C#
- Pros and Cons of Multiple Constructors
- More...

- Making Your C# Code More Object-oriented
- Making Your C# Code More Functional
- Writing Purely Functional Code in C#
- Tactical Design Patterns in .NET: Creating Objects
- Tactical Design Patterns in .NET: Control Flow
- Tactical Design Patterns in .NET: Managing Responsibilities
- Advanced Defensive Programming Techniques
- Writing Highly Maintainable Unit Tests
- Improving Testability Through Design