LESSON 146 OF 414 · LOOPS & GLOBAL VARIABLES

Sum of Squares in Rust: A for Loop with an Accumulator

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

Problem overview

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

Approach

The sum is built one term at a time. A variable called sum starts at 0, which means nothing has been added yet. A loop then visits each number i from 1 to n, and each pass adds the square of i to sum. When the loop ends, sum holds the answer and the function returns it.

For n = 3 the variable goes through these values:

Before the loop: sum is 0.
With i = 1: sum becomes 0 + 1 = 1.
With i = 2: it becomes 1 + 4 = 5.
With i = 3: it becomes 5 + 9 = 14.

There is also a closed-form formula, n * (n + 1) * (2 * n + 1) / 6, which gives the same result without a loop. This lesson practises the loop, so it builds the sum term by term.

Step by step

Declare the accumulator. Write let mut sum = 0;. It needs mut because the loop changes it. Rust infers the type i32 from the function's return type, so no annotation is needed.
Loop from 1 to n inclusive. Use the range 1..=n. The plain range 1..n would stop at n - 1 and leave out the last square.
Add each square. Inside the loop, sum += i * i; multiplies i by itself and adds the product.
Return the total after the loop has finished.

The solution in Rust

impl Solution {
    fn sum_of_squares(n: i32) -> i32 {
        let mut sum = 0;
        for i in 1..=n {
            sum += i * i;
        }
        return sum;
    }
}

Some Rust details here:

Inclusive range. 1..=n includes n. When n is 0, the range is empty and the loop body never runs, so the function returns 0, which is correct.
Type inference. The literal 0 has no type of its own. Because sum is returned from a function declared to return i32, and i comes from the i32 range 1..=n, the compiler makes everything i32.
No exponent operator. Rust has no **. A square is written as i * i, or as i.pow(2) for an integer.
Immutable by default. Without mut, sum += i * i; is a compile error.

Complexity

Time: O(n). The loop runs n times and does a constant amount of work on each pass: one multiplication and one addition.

Space: O(1). The function stores only sum and the loop variable.

Edge cases and common mistakes

n = 0. The result is 0, because the loop runs zero times.
n = 1. The result is 1.
Stopping one short. With 1..n in place of 1..=n, sum_of_squares(3) would return 1 + 4 = 5 instead of 14.
Starting at 0. It is harmless here, since 0 squared adds nothing, but the sum is defined from 1.
Adding i instead of i * i. That computes the plain sum 1 + 2 + 3 = 6.
Overflow. The result is an i32, and it only fits up to n = 1860, where the sum is 2,146,682,110, just under the limit of 2,147,483,647. With n = 1861 the true sum is 2,150,145,431, which does not fit. In an optimized build the value wraps around silently and gives a negative number for n = 2000, and in a debug build the same overflow panics.

Testing

n = 3 gives 14.
n = 0 gives 0.
n = 1 gives 1.
n = 2 gives 5.
n = 10 gives 385.
n = 100 gives 338350.

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

Start learning free