Start learning free

LESSON 165 OF 348 · LOOPS - CHALLENGES

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

    KOTLIN · LOOPS - CHALLENGES

    Find Largest Number in Kotlin, explained

    Problem overview

    The function findLargestNumber(S: Int) receives a positive number S. It must return the largest n for which 1² + 2² + 3² + ... + n² is less than or equal to S.

    For S = 35 the answer is 4. The sum up to 4 is 1 + 4 + 9 + 16 = 30, which is at most 35. Adding 5² = 25 would give 55, which is over the limit, so 5 is too large.

    Approach

    The squares are all positive, so the running sum only grows as n grows. That means the answer is the point where adding one more square would cross S. The simplest method is to add the squares one at a time, starting from 1, and stop just before the sum would go over S.

    The loop therefore needs two variables: the sum so far, and the number whose square comes next. The condition looks one square ahead. If adding the next square still fits, add it and move on; if not, the last number added is the answer.

    Step by step

    1. The running sum. var totalSoFar = 0 holds the sum of the squares added so far. It starts at 0 because nothing has been added.
    2. The next number. var number = 1 is the number whose square is added next, because the sum begins with 1².
    3. The loop condition. while (totalSoFar + number * number <= S) asks whether the sum would still be within S after adding the next square. Checking before adding keeps totalSoFar from ever going over the limit.
    4. Add the square. totalSoFar += number * number includes the current term.
    5. Move on. number++ makes the next pass consider the following square. Without it, the same condition would stay true forever.
    6. Correct the final value. When the loop stops, number is the first number whose square did not fit, one past the last number added. Returning number - 1 gives the answer.

    With S = 35 the loop adds 1, 4, 9 and 16, reaching 30 with number equal to 5. The condition then asks whether 30 + 25 is at most 35, which is false, so the loop ends and the function returns 4.

    The solution in Kotlin

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

    Kotlin details:

    • var for both variables. Both change in the loop, so a val would not compile.
    • Int is 32 bits and overflow wraps silently. Kotlin doesn't warn when an Int goes past 2147483647. It wraps around to a negative number. See the edge cases below for how this affects large S.
    • number++ adds 1 to the variable and, used as a statement like this, has the same effect as number += 1.
    • Operator precedence. * binds tighter than +, and + binds tighter than <=, so the condition needs no extra parentheses.

    Complexity

    The sum of the first n squares is n(n + 1)(2n + 1) / 6, which grows like n³ / 3. So the loop runs about (3S)^(1/3) times, the cube root of 3S. For S = 35 that is 4 passes.

    Time: O(S^(1/3)), which is far below O(S). For S = 1,000,000 the loop runs 143 times.

    Space: O(1). The function uses two variables.

    Edge cases and common mistakes

    • Small S. For S = 1 the loop adds 1² and the answer is 1. If S were smaller than 1, no square fits, the loop never runs and the function returns 0.
    • A sum that lands exactly on S. S = 5 gives 2, because 1 + 4 = 5 is allowed. The condition uses <=, not <. With < the function would return 1 for S = 5.
    • Just below a sum. The sums of 1, 2 and 3 terms are 1, 5 and 14. So S = 13 gives 2, because 14 doesn't fit, while S = 14 gives 3.
    • Returning number instead of number - 1. The loop ends one step after the last successful addition, so the answer would be one too high.
    • Checking after adding. A loop that adds first and tests afterwards can end with a sum that's already over S, and the answer is again one too high.
    • Overflow for very large S. The sum of squares reaches the Int limit near S = 2147483647. For S = 2147000000, the correct answer is 1860, but with Int variables the expression totalSoFar + number * number wraps to a negative value after the sum passes the limit, the condition stays true, and the function returns 8548. If S can be that large, declare totalSoFar and number as Long and compare with S.toLong().

    Testing

    • S = 35 gives 4.
    • S = 1 gives 1.
    • S = 5 gives 2.
    • S = 14 gives 3, and S = 15 also gives 3.
    • S = 55 gives 5.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free