Start learning free

LESSON 165 OF 348 · LOOPS - CHALLENGES

Find Largest Number in TypeScript: Sum of Squares with a while Loop

Practice Read the full explanation

Given a positive number S, find the largest number n such that the sum
12 + 22 + 32 + ... + n2 is less than or equal to S.

For your information, n2 = n * n

Example:

Input: S = 35

Output: 4

Explanation:
12 + 22 + 32 + 42 = 1 + 4 + 9 + 16 = 30
and 30 <= 35
if we add 52 we end up with 55, which exceeds 35
therefore 4 is the answer
Hints:

If we look at the explanation, a simple algorithm comes to mind:
Keep track of the totalSoFar and start iterating from 1 as long as adding number * number to totalSoFar is less than or equal to S.
You continue to add number * number to totalSoFar as long as you don't exceed S
STEP 1 OF 6
    Ctrl + Enter to check

    TYPESCRIPT · LOOPS - CHALLENGES

    Find Largest Number in TypeScript, explained

    Problem overview

    Given a positive number S, the method findLargestNumber(S) returns the largest integer n for which 1² + 2² + 3² + ... + n² is less than or equal to S.

    For S = 35 the sums are 1, 5, 14, 30 and then 55. Four squares give 30, which fits within 35, but adding 5² = 25 would give 55, which doesn't. The answer is 4.

    Approach: add squares until the next one doesn't fit

    No formula is needed. Keep a running total and a counter for the next number to add. Each round asks one question: if I add the square of the counter, is the total still at most S? If yes, add it and move the counter up. If no, stop.

    The check looks one square ahead and the total only changes after the check passes. That means the total never exceeds S, so no undoing is needed afterwards. Because the counter moves up after every successful addition, it ends one past the last number that was added, and the answer is the counter minus one.

    Step by step

    1. Declare totalSoFar with let and set it to 0, since nothing has been added yet.
    2. Declare number with let and set it to 1, the first number whose square is added.
    3. Write the loop with the condition totalSoFar + number * number <= S. It tests the sum that would result, without changing anything.
    4. Add the square to the total with += inside the loop.
    5. Increment number so the next round tests the following square. Without this line the loop would never end.
    6. Return number - 1 after the loop. For S = 35 the loop adds 1, 4, 9 and 16, then stops with number equal to 5, because 30 + 25 exceeds 35. The answer 4 is one less.

    The solution in TypeScript

    class Solution {
    findLargestNumber(S: number): number {
        let totalSoFar: number = 0;
        let number: number = 1;
        while (totalSoFar + number * number <= S) {
            totalSoFar += number * number;
            number++;
        }
        return number - 1;
    }
}

    The variable named number has the same name as the type number. That is legal because types and variables live in separate places: in let number: number = 1 the first word is a variable name and the one after the colon is the type. It is confusing to read, though, and a name such as current would be clearer in your own code.

    TypeScript's number is a double-precision floating-point value, so S could be any number, not only an integer, and the loop still works: it compares the sums with S as written. The variables hold whole numbers here, and sums stay exact up to 2^53, far beyond any reasonable input.

    Complexity

    The sum of the first n squares is about n³ / 3, so the loop stops when n is around the cube root of 3S. The time is therefore O(S^(1/3)), which is very fast: for S near a billion, the loop runs about 1,400 times. It uses two variables, so the extra space is O(1).

    Edge cases and common mistakes

    • S smaller than 1. The first check, 0 + 1 <= S, is false, so the loop never runs and the method returns 0. No positive number has a square sum within S, and 0 stands for "none".
    • S = 1. One square fits and a second would give 5, so the answer is 1.
    • An exact fit. For S = 30 the sum 30 is allowed because the condition uses <=. The answer is 4. Using < would wrongly return 3.
    • Returning number instead of number - 1. That is the number that did not fit.
    • Adding first and checking afterwards. Then the total can overshoot S and the counter ends two past the answer.

    Testing

    Try S = 35 (answer 4), S = 55 (answer 5, because 1 + 4 + 9 + 16 + 25 = 55) and S = 3 (answer 1).

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