Start learning free

LESSON 164 OF 347 · LOOPS - CHALLENGES

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

    C# · LOOPS - CHALLENGES

    Find Largest Number in C#, explained

    Problem overview

    FindLargestNumber(int S) looks for the largest n for which 1² + 2² + 3² + ... + n² is at most S.

    For S = 35: the running sums are 1, 5, 14 and 30 after adding the squares of 1, 2, 3 and 4. Adding 5² = 25 would make 55, which is above 35. So the answer is 4.

    Approach

    Keep a running total of the squares added so far, and try the numbers 1, 2, 3, ... in order. Before adding the next square, check whether the total would still be at most S. If it would, add it and move on. If not, stop: the squares are positive, so no later number can fit either.

    This is a while loop, because the number of repetitions depends on S and isn't known beforehand. The key is that the condition looks one square ahead. The loop never lets the total go above S, so when it ends the total is valid and the next number is the first one that doesn't fit.

    Step by step

    1. Create the running total. totalSoFar starts at 0, because nothing has been added yet.
    2. Create the next number to try. number starts at 1, since the sum begins with 1².
    3. Write the loop condition. totalSoFar + number * number <= S asks whether adding the next square still fits.
    4. Add the square. totalSoFar += number * number includes the current number in the sum.
    5. Advance. number++ moves to the following number. Without it, the loop would add the same square forever.
    6. Return one less than number. After the last successful addition, number was incremented once more, so it points one past the answer.

    Tracing S = 35

    Before the checktotalSoFarnumberTest
    Pass 1010 + 1 <= 35, so add
    Pass 2121 + 4 <= 35, so add
    Pass 3535 + 9 <= 35, so add
    Pass 414414 + 16 <= 35, so add
    Pass 530530 + 25 = 55 > 35, so stop

    The loop ends with number equal to 5, and the function returns 5 - 1 = 4.

    The solution in C#

    class Solution {
    public int FindLargestNumber(int S) {
        int totalSoFar = 0;
        int number = 1;
        while (totalSoFar + number * number <= S) {
            totalSoFar += number * number;
            number++;
        }
        return number - 1;
    }
}

    Some C# details:

    • There is no ^ for powers. In C#, ^ is a bitwise operator (exclusive or). Write a square as number * number, or use Math.Pow, which works on double and would need a cast back to int. Plain multiplication is simpler and exact.
    • Integer arithmetic stays integer. All three variables are int, so there is no rounding to worry about.
    • number++ adds 1 to the variable. It is a statement here, so the prefix or postfix form makes no difference.

    Complexity

    Time. The sum of the first n squares is about n³ / 3, so the loop stops once n reaches roughly the cube root of 3S. So the number of passes is proportional to the cube root of S, which is very small. Even for S near two billion, the loop makes under two thousand passes.

    Space: O(1). Only two integer variables are used.

    Edge cases and common mistakes

    • Small S. For S = 1 the loop adds 1, then 1 + 4 exceeds the limit, so the answer is 1. If S were below 1, the loop wouldn't run and the function would return 0, which is also correct because no square fits.
    • An exact fit. For S = 30 the sum equals the limit after 4, and the answer is 4. That is why the comparison is <= and not <.
    • Returning number. That is one too many. The loop leaves number at the first value that didn't fit.
    • Checking after adding. A loop that adds first and tests afterwards would include a square that pushes the total over S, then have to take it back out.
    • Overflow for huge S. int arithmetic wraps silently in C#. When S is within about a million of int.MaxValue, the expression totalSoFar + number * number can exceed the int range, wrap to a negative value and pass the test. With S = 2147000000, for example, the function returns 8548 instead of 1860. Using long for the total avoids that. Inputs of ordinary size are not affected.

    Testing

    • S = 35 gives 4.
    • S = 30 gives 4.
    • S = 5 gives 2.
    • S = 1 gives 1.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free