LESSON 185 OF 415 · LOOPS - CHALLENGES

Find Largest Number in Swift: Summing Squares in a while Loop

Given a positive number S, find the largest number n such that the sum
1² + 2² + 3² + ... + n² is less than or equal to S.

For your information, n² = n * n

Example:

Input: S = 35

Output: 4

Explanation:
1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30
and 30 <= 35
if we add 5² 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

Guided

Ctrl + Enter to check

Find Largest Number in Swift, explained

Problem overview

The method findLargestNumber(_ S: Int) takes a positive number S and returns the largest n for which 1² + 2² + 3² + ... + n² is at most S. For S = 35 the sums are 1, 5, 14 and 30 for n = 1 to 4, and adding 5² = 25 would give 55, which is more than 35. The answer is 4.

Approach

Add the squares one at a time and stop just before the sum would go over S. Two variables are enough: totalSoFar, the sum of the squares added so far, and number, the next number whose square is considered. Because every square is positive, the sum only grows, so the first square that doesn't fit ends the search for good: no larger n can work.

The loop condition looks one step ahead: totalSoFar + number * number <= S asks whether adding the next square still fits. The body then performs the addition. That way totalSoFar never exceeds S.

Step by step

Declare totalSoFar as var, set to 0. Nothing has been added yet.
Declare number as var, set to 1. The sum starts with 1².
Write the while loop with the condition totalSoFar + number * number <= S.
Add the square: totalSoFar += number * number.
Increment: number += 1. Swift has no ++ operator, so += 1 is the form to use. Without this line the loop would never end.
Return number - 1. After the last successful addition number was incremented once more, so it points one past the answer.

The solution in Swift

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

Tracing S = 35: the checks are 0 + 1 <= 35, 1 + 4 <= 35, 5 + 9 <= 35 and 14 + 16 <= 35, all true. After the fourth pass totalSoFar is 30 and number is 5. The next check is 30 + 25 <= 35, which is false, so the loop ends and the method returns 5 - 1 = 4.

Swift details:

var declares a variable that can change, let one that cannot. Both counters change, so both are var.
Int is 64 bits. Arithmetic that overflows traps and crashes the program instead of wrapping around. Here the sums stay far below that limit unless S is close to the maximum Int.
No parentheses are needed around the condition, and the braces are required.

Complexity

Time: the sum 1² + ... + n² is about n³ / 3, so the loop stops when n is roughly the cube root of 3 * S. Time is therefore O(S^(1/3)), which is much less than O(S). If you describe it by the answer n instead, it is O(n). Space: O(1), two integers.

Edge cases and common mistakes

S smaller than 1. With S = 0, the first check 0 + 1 <= 0 is false, so the loop never runs and the method returns 0. No positive number fits.
S exactly equal to a sum. For S = 30 the answer is 4, because the condition uses <=. With S = 29 the answer drops to 3.
Checking after adding. If the loop adds the square first and tests the total afterwards, the last addition may already have gone over S, and the returned value is too large.
Returning number. It is one past the answer. For S = 35 it would return 5.
Forgetting the increment, which makes an infinite loop.

Testing

S = 35 gives 4.
S = 30 gives 4.
S = 29 gives 3.
S = 1 gives 1.
S = 0 gives 0.

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

Start learning free