by Zoran Horvat

Dec 14, 2013

Given a positive number N, write a function which returns sum of numbers 1 + 2 + ... + N.

Example: If N is 5, then return value should be 15 (1 + 2 + 3 + 4 + 5 = 15).

This task can be solved quickly by iterating through the sequence:

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

This function runs in time O(N) and space O(1). Now we can ask if there is a better solution in terms of running time. In order to make the function run in constant time, we need to entail a definite form of the sum. This is easy to do and here is one possible way:

The function which calculates the sum of the sequence in O(1) time and O(1) space is then:```
function Sum(n)
begin
return n * (n + 1) / 2
end
```

Below is the console application in C# which lets the user enter N and then prints the sum of the sequence of N elements.

```
using System;
namespace SumOfSequence
{
public class Program
{
static int Sum(int n)
{
return n * (n + 1) 2;
}
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));
}
}
}
}
```

Here is the possible output of the application listed above:

```
Enter sequence length (zero to exit): 4
Sum of the sequence is 10
Enter sequence length (zero to exit): 5
Sum of the sequence is 15
Enter sequence length (zero to exit): 43127
Sum of the sequence is 929990628
Enter sequence length (zero to exit): 0
```

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

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.

- 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
- Defensive Design: An Experiment
- 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