Start learning free

LESSON 184 OF 414 · LOOPS - CHALLENGES

Find Largest Number in Scala: 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

    SCALA · LOOPS - CHALLENGES

    Find Largest Number in Scala, explained

    Problem overview

    The method findLargestNumber(S: Int) returns the largest n for which 1² + 2² + 3² + ... + n² is at most S. The sum of squares grows with every term, so the answer is the point where adding one more square would go over the limit.

    For S = 35 the running sums are 1, 5, 14 and 30. Adding 5² = 25 would give 55, which is more than 35, so the answer is 4.

    Approach

    Add the squares one at a time and stop before the sum exceeds S. Keep two variables: totalSoFar holds the sum of the squares added so far, and number is the next base to square. The loop condition looks one square ahead: totalSoFar + number * number <= S. When it fails, adding number would break the limit, so the answer is the number before it.

    No formula is needed. The sum of the first n squares does have a closed form, but the loop is simple, and since the sum grows roughly like n³ / 3, it stops after only a few passes even for large S.

    Step by step

    1. Start the sum at 0. var totalSoFar = 0 holds the squares added so far. Nothing has been added yet.
    2. Start counting at 1. var number = 1 is the base of the next square, because the sum begins with 1².
    3. Write the loop condition. while (totalSoFar + number * number <= S) asks whether the next square still fits. Checking before adding means totalSoFar never goes above S.
    4. Add the square. totalSoFar += number * number includes this term in the running sum.
    5. Move to the next number. number += 1 is required: without it the loop never ends. Scala has no ++ operator, so use += 1.
    6. Return number - 1. After the last successful pass, number was incremented once more, so it sits one past the last number that fit.

    With S = 35, the loop adds 1, 4, 9 and 16, reaching a total of 30 with number equal to 5. Then 30 + 25 = 55 is more than 35, the loop stops, and the method returns 4.

    The solution in Scala

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

    Some Scala details:

    • Two vars. Both values change inside the loop, so neither can be a val. Scala infers Int for both from the literals.
    • Compound assignment. totalSoFar += number * number multiplies first and then adds, because * binds tighter than +=.
    • Parameter names. The parameter is the capital S, as in the method signature. Scala is case-sensitive, so s would be a different name.
    • Optional return. The last expression of a block is its value, so ending with number - 1 alone would work as well. The explicit return is allowed here, because it is not inside a lambda.

    Complexity

    Time: O(S^(1/3)). The loop stops when the sum of the first n squares passes S. That sum is about n³ / 3, so n is about the cube root of 3S. Each pass is constant work. In terms of the answer n, the time is O(n).

    Space: O(1). Two integers are all that is stored.

    Edge cases and common mistakes

    • Exact hit. When the sum equals S, the condition uses <=, so that term is included. For S = 30 the answer is 4, since 1 + 4 + 9 + 16 is exactly 30.
    • Small S. For S = 1 the answer is 1. For S = 4 it is still 1, because 1 + 4 = 5 is above 4. For S = 5 it is 2.
    • Checking after adding. If the loop adds first and tests the sum afterwards, the sum overshoots S before the loop notices, and the result is off by one.
    • Forgetting the - 1. Returning number gives 5 for S = 35.
    • Overflow. Int is 32 bits and overflow wraps silently. For values of S near Int.MaxValue, the sum or number * number can wrap to a negative value that passes the test. Use Long if S can be that large.

    Testing

    • S = 35 gives 4.
    • S = 1 gives 1.
    • S = 4 gives 1.
    • S = 5 gives 2.
    • S = 55 gives 5, because 1 + 4 + 9 + 16 + 25 = 55.
    • S = 100 gives 6.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free