Problem overview
The function findLargestNumber receives a positive integer S. It must return the largest n for which the sum 1² + 2² + 3² + ... + n² is less than or equal to S.
For S = 35: the sums grow as 1, 5, 14, 30 and then 55. The sum for n = 4 is 30, which is at most 35. The sum for n = 5 would be 55, which is over. So the answer is 4.
Approach: add squares until the next one doesn't fit
The sum only ever grows, because every square is positive. That means that once adding a square would push the total above S, no larger n can work either. So a single pass is enough: add 1², then 2², then 3², and so on, and stop right before the addition that would exceed S.
Two variables carry the state: totalSoFar, the sum of the squares added so far, and number, the next number whose square is waiting to be added. The loop condition looks one step ahead, asking whether totalSoFar + number * number is still at most S. If it is, the square is added; if not, the loop ends and totalSoFar never goes over S.
Step by step
- Start the total at 0. Declare
totalSoFarwith:=. Nothing has been added yet. - Start the counter at 1. Declare
numberwith:=. The sum starts with 1². - Loop on a condition. Go has no
while, so use aforwith only a condition: continue whiletotalSoFar + number * number <= S. This checks the next square before adding it. - Add the square of
numbertototalSoFarwith+=. - Move to the next number. Increase
numberby 1. Without this the condition never changes and the loop doesn't end. - Return
number - 1. When the loop stops,numberis the first value whose square did not fit. The last value that fit is one less.
The solution in Go
func findLargestNumber(S int) int {
totalSoFar := 0
number := 1
for totalSoFar + number * number <= S {
totalSoFar += number * number
number += 1
}
return number - 1
}
On S = 35 the loop adds 1, 4, 9 and 16 and reaches number = 5 with totalSoFar = 30. Then 30 + 25 = 55 is more than 35, so the loop stops and the function returns 4.
Go details worth knowing:
- Condition-only
for.for cond { ... }is Go'swhile. The condition has no parentheses and is re-evaluated before every iteration, including the first. - Operator precedence. In
totalSoFar + number * number <= S, multiplication binds tighter than addition, and addition binds tighter than the comparison. No parentheses are needed.gofmtwould format this astotalSoFar+number*number <= S; both mean the same. number += 1. Go also hasnumber++, but it is a statement, not an expression. You can't writex = number++or use it inside a condition.- Integers only. All three values are
int, so there is no rounding. Anintis 64 bits and overflow wraps silently, but a square of the size needed to pass any realisticSis far from that limit.
Complexity
The sum of the first n squares is about n³ / 3. For the loop to stop, that sum must exceed S, so the answer n is about the cube root of 3 * S.
Time: O(S^(1/3)). The loop runs once per value of number, which is the answer plus one, so it runs about the cube root of 3S times. It is sometimes simpler to say it is O(S) at worst, which is true but loose.
Space: O(1). Two integer variables, whatever the value of S.
Edge cases and common mistakes
- Returning
numberinstead ofnumber - 1. After the loop,numberis the first value that did not fit. ForS = 35that would be 5, not 4. - Checking the total after adding. If the loop added the square first and tested afterwards, the total would overshoot
Sonce before stopping, and the answer would be off by one. Looking ahead in the condition avoids that. - Using
<instead of<=. When a sum equalsSexactly, it is allowed. ForS = 5, 1 + 4 = 5 counts, so the answer is 2. With<it would be 1. - Small values. For
S = 1the answer is 1. ForS = 0, which the task excludes, the loop doesn't run and the function returns 0. - Forgetting
number += 1. The same square is added again and again, until the total passesS, and the function returns 0. It still ends, but with a wrong answer.
Testing
S = 35gives4.S = 1gives1.S = 5gives2.S = 14gives3, since 1 + 4 + 9 = 14 exactly.