http://www.codinghelmet.com/  

Wear a helmet. Even when coding.

exercises > sum-of-squares-first-n

Exercise #18: Sum of Squares of First N Numbers
by Zoran Horvat @zoranh75

Problem Statement
by Zoran Horvat @zoranh75

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).

Problem Analysis

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:

S=N(N+1)(2N+1)/6

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

Implementation

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));

            }

        }

    }
}

Demonstration

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

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 design patterns, writing unit and integration tests and applying methods to improve code design and long-term maintainability.

Follow him on Twitter @zoranh75 to receive updates and links to new articles.

Watch Zoran's video courses at pluralsight.com (requires registration):

Tactical Design Patterns in .NET: Managing Responsibilities

Applying a design pattern to a real-world problem is not as straightforward as literature implicitly tells us. It is a more engaged process. This course gives an insight into 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...

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

webmasters