LESSON 137 OF 338 · LOOPS & GLOBAL VARIABLES

Sum of Squares in Go: Accumulating with a for Loop

Given a non-negative integer n, compute and return the sum of
1² + 2² + 3² + ... + n²

Example:

Input: n = 3

Output: 14

Explanation:
1² + 2² + 3² = 1 + 4 + 9 = 14

Hints:

Where should we store this sum as we compute it?

We can use a variable sum, initially equal to 0. We have to iterate through the numbers 1 to n. How can we do this?

Let's use a for loop and a variable i to iterate through the numbers 1 to n. What should we do inside this loop?

Inside the loop, all we should do is add i * i to sum.
When the loop terminates, the answer lies in sum.

STEP 1 OF 4

Guided

Ctrl + Enter to check

Sum Of Squares in Go, explained

Problem overview

The function sumOfSquares receives a non-negative integer n and returns 1*1 + 2*2 + ... + n*n. For n = 3 that is 1 + 4 + 9 = 14. For n = 0 there are no terms, so the sum is 0.

Approach: an accumulator and a counter

The terms follow a clear pattern, so a loop can produce them. Keep a variable sum that holds the total so far, starting at 0 because nothing has been added. Let a counter i run from 1 to n, and on each pass add i * i to sum. When the loop ends, sum holds the answer.

For n = 3, the passes go like this: i = 1 makes the sum 1, i = 2 makes it 5, and i = 3 makes it 14.

Step by step

Declare sum with := and the value 0. Go infers the type int.
Write the loop. Declare i with := and start it at 1. Keep going while i <= n, so that n itself is included, and add 1 each pass with i++.
Add the square. Inside the loop, sum += i * i adds the current term.
Return sum after the loop.

The solution in Go

func sumOfSquares(n int) int {
    sum := 0
    for i := 1; i <= n; i++ {
        sum += i * i
    }
    return sum
}

Go details:

No parentheses in the loop header. The three parts are separated by semicolons, and the braces are required.
:= declares, = assigns. sum := 0 creates the variable. After that, sum += i * i updates it. Declaring sum inside the loop would create a fresh variable each pass and leave nothing to return.
No exponent operator. Go has no ** or ^ for powers, so the square is written as i * i. The standard library function math.Pow works on float64, which is the wrong tool for exact integer squares.
Typed arithmetic. i and sum are both int, so no conversion is needed.

Why the loop starts at 1 and ends at n

The two bounds come straight from the definition of the sum. The first term is 1 squared and the last is n squared, so the counter must take every whole value from 1 to n, and each exactly once. A loop condition of i <= n expresses "up to and including n". When a task names both ends of a range, check each end against the loop header before running the code. Most mistakes in loops like this come from one bound being off by one.

Complexity

Time: O(n). The loop makes exactly n passes, each with one multiplication and one addition.

Space: O(1). Only sum and i are stored. A closed formula, n * (n + 1) * (2 * n + 1) / 6, would give the answer in constant time, but this lesson practises the loop.

Edge cases and common mistakes

n = 0. The condition 1 <= 0 is false at once, the loop never runs, and the function returns 0.
n = 1. One pass adds 1, and the result is 1.
Using i < n. That leaves out the last term. For n = 3 it would give 1 + 4 = 5.
Starting at 0. That still gives the right result, because 0 squared is 0, but it adds a pointless pass. The task's sum starts at 1.
Adding i instead of i * i. That computes 1 + 2 + 3 = 6 for n = 3.
Squaring the running total. Writing sum = sum * sum or similar squares the wrong thing. Square the counter, and add.
Overflow. The sum grows roughly like n cubed divided by 3, so a 64-bit int overflows only for n around three million. Go wraps silently instead of reporting it.

Testing

sumOfSquares(3) gives 14.
sumOfSquares(0) gives 0.
sumOfSquares(1) gives 1.
sumOfSquares(10) gives 385.

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free