LESSON 142 OF 414 · LOOPS & GLOBAL VARIABLES

Sum of Squares in Scala: a for Loop with a Running Total

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 Scala, explained

Problem overview

The method sumOfSquares receives a non-negative integer n and returns 1² + 2² + 3² + ... + n². For n = 3 the terms are 1, 4 and 9, so the answer is 14. For n = 0 there are no terms to add, and the answer is 0.

Approach: accumulate in a variable

The sum is built one term at a time. Keep a variable that starts at 0, visit every number from 1 to n, and add the square of each number to the variable. When the loop ends, the variable holds the whole sum. This is the standard accumulator pattern, and it is the same shape you will use for products, counts and maximums later in the chapter.

The work is one addition per number, so the time is proportional to n, and the only extra memory is the running total and the loop variable.

Step by step

Declare sum with var and start it at 0. It has to change inside the loop, so val would not work: a val can't be reassigned. Starting at 0 means "nothing added yet", and 0 doesn't affect an addition. Scala infers the type Int from the literal.
Loop with for (i <- 1 to n). The expression 1 to n is a range that includes both ends. The arrow <- reads "for each i taken from this range".
Add i * i to sum with +=. The line sum += i * i is shorthand for sum = sum + i * i. The multiplication happens first.
Return sum after the loop. The loop only collects the terms; the method still has to hand the result back.

The solution in Scala

class Solution {
    def sumOfSquares(n: Int): Int = {
        var sum = 0
        for (i <- 1 to n) {
            sum += i * i
        }
        return sum
    }
}

For n = 3 the loop runs three times:

`i`	Added	`sum` afterwards
1	1	1
2	4	5
3	9	14

Language details

1 to n and 1 until n differ by one element. to includes n, until stops before it. With until the answer for n = 3 would be 1 + 4 = 5.
When n is 0, 1 to 0 is an empty range. The loop body never runs and the method returns the initial 0, which is correct without a special case.
Scala has no ++ operator, which is why the update is written +=.
The last expression of a block is its value in Scala, so a version that ends with just sum would also work. The lesson uses an explicit return, which is fine here.

Complexity

The loop runs exactly n times and each pass does a constant amount of work, so the time is O(n). The method stores only sum and the loop variable, so the extra space is O(1).

Edge cases and common mistakes

Using until instead of to. This leaves out n² and gives a result that is too small.
Starting the range at 0. It is harmless, since 0 squared is 0, but it does one pointless pass.
Declaring sum inside the loop. Then it starts again from 0 on every pass and only the last square survives.
Int overflow. An Int holds values up to 2147483647 and wraps silently past that. The sum for n = 1000 is 333833500, which fits, but sumOfSquares(2000) returns -1626300296, because the true value 2668667000 is too large. A Long would be needed for bigger inputs.

Testing

Good inputs to try: n = 0 gives 0, n = 1 gives 1, n = 3 gives 14 and n = 10 gives 385.

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

Start learning free