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

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