Start learning free

LESSON 137 OF 348 · LOOPS & GLOBAL VARIABLES

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

Practice Read the full explanation

Given a non-negative integer n, compute and return the sum of
12 + 22 + 32 + ... + n2

Example:

Input: n = 3

Output: 14

Explanation:
12 + 22 + 32 = 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
    Ctrl + Enter to check

    TYPESCRIPT · LOOPS & GLOBAL VARIABLES

    Sum Of Squares in TypeScript, explained

    Problem overview

    The method sumOfSquares receives a non-negative integer n and returns 1^2 + 2^2 + 3^2 + ... + n^2. 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 sum is 0.

    Approach: keep a running total

    The pattern is the same as adding a column of numbers on paper. Start with a total of 0, visit each number from 1 to n once, square it, and add the square to the total. When the last number has been added, the total is the answer.

    Three pieces are needed: a variable that lives for the whole method (the total), a loop that produces the numbers 1 to n, and one line in the loop body that updates the total. Because the loop runs n times and each pass does a fixed amount of work, the method takes time proportional to n.

    Step by step

    1. Declare the total. It is called sum, it has the type number, and it starts at 0 because nothing has been added yet. It is declared with let, not const, since the loop changes its value.
    2. Write the loop header. The index i starts at 1, the first number to square. The condition is i <= n, with <= so that n itself is included; with < the last square would be missing. i++ moves to the next number after each pass.
    3. Add the square. Inside the loop, sum += i * i squares the current number and adds it to the total. The operator += is shorthand for sum = sum + i * i.
    4. Return the total. The return goes after the loop, once every square has been added. Putting it inside the loop would end the method during the first pass.

    The solution in TypeScript

    class Solution {
    sumOfSquares(n: number): number {
        let sum: number = 0;
        for (let i = 1; i <= n; i++) {
            sum += i * i;
        }
        return sum;
    }
}

    A few TypeScript details are worth knowing:

    • Annotations are for the compiler only. The : number in let sum: number = 0 and the : number return type are checked when the code is compiled, then removed from the JavaScript that runs. TypeScript would infer the type of sum from the 0 anyway, so the annotation here is optional.
    • let i belongs to the loop. A variable declared in the loop header exists only inside the loop, so a later i in the same method would be a separate variable.
    • There is no int type. Every number is a double-precision float. Squares of whole numbers are exact as long as the values stay below 2^53, about 9 quadrillion.
    • i * i or i ** 2. TypeScript has an exponent operator, **, but multiplying a number by itself is clear and needs no explanation.

    Complexity

    Time: O(n). The loop body runs exactly n times, and each pass is a multiplication and an addition.

    Space: O(1). The method uses only sum and i, no matter how large n is.

    A closed formula, n(n + 1)(2n + 1) / 6, would give the answer without a loop. The loop is the point of this lesson, and it is the pattern you will reuse whenever a result is built from many small pieces.

    Edge cases and common mistakes

    • n = 0. The condition 1 <= 0 is false at once, the loop body never runs, and the method returns the starting value 0. That is the correct answer.
    • n = 1. The loop runs once and the result is 1.
    • Starting at 0. It is harmless here because 0 squared is 0, but it does one pointless pass.
    • Using < instead of <=. For n = 3 the method would return 5 (1 + 4) instead of 14.
    • Adding i instead of i * i. That computes 1 + 2 + ... + n, which is 6 for n = 3.
    • Resetting the total inside the loop. If let sum = 0 sat inside the loop, each pass would start from zero and the method would return only the last square.
    • Very large n. Past 2^53 a number can no longer hold every integer. Computing sumOfSquares(1000000) with this loop gives 333333833333127550, while the exact value is 333333833333500000. For inputs of ordinary size, such as n = 300000, whose answer is 9000045000050000, the result is exact.

    Testing

    • sumOfSquares(3) gives 14.
    • sumOfSquares(0) gives 0.
    • sumOfSquares(1) gives 1.
    • sumOfSquares(10) gives 385.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free