Exercise #17: Sum of First N Numbers by Zoran Horvat @zoranh75
Problem Statement
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).
Problem Analysis
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
Implementation
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));
}
}
}
}
Demonstration
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
See also:
Published: Dec 14, 2013
ZORAN HORVAT Zoran is software architect dedicated to clean design and CTO in a growing software company. Since 2014 Zoran is an author at Pluralsight where he is preparing a series of courses on objectoriented and functional design, design patterns, writing unit and integration tests and applying methods to improve code design and longterm maintainability. Follow him on Twitter @zoranh75 to receive updates and links to new articles. Watch Zoran's video courses at pluralsight.com (requires registration): Making Your C# Code More ObjectOriented This course will help leverage your conceptual understanding to produce proper objectoriented code, where objects will completely replace procedural code for the sake of flexibility and maintainability. More... Advanced Defensive Programming Techniques This course will lead you step by step through the process of developing defensive design practices, which can substitute common defensive coding, for the better of software design and implementation. More... Tactical Design Patterns in .NET: Creating Objects This course sheds light on issues that arise when implementing creational design patterns and then provides practical solutions that will make our code easier to write and more stable when running. More... Tactical Design Patterns in .NET: Managing Responsibilities Applying a design pattern to a realworld problem is not as straightforward as literature implicitly tells us. It is a more engaged process. This course gives an insight to tactical decisions we need to make when applying design patterns that have to do with separating and implementing class responsibilities. More... Tactical Design Patterns in .NET: Control Flow Improve your skills in writing simpler and safer code by applying coding practices and design patterns that are affecting control flow. More... Writing Highly Maintainable Unit Tests This course will teach you how to develop maintainable and sustainable tests as your production code grows and develops. More... Improving Testability Through Design This course tackles the issues of designing a complex application so that it can be covered with high quality tests. More... Share this article
