Start learning free

LESSON 187 OF 414 · LOOPS - CHALLENGES

Find Largest Number in Rust: A while Loop on Squares

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

    RUST · LOOPS - CHALLENGES

    Find Largest Number in Rust, explained

    Problem overview

    Given a positive number S, find the largest n for which 1*1 + 2*2 + ... + n*n is less than or equal to S. The function is find_largest_number; it takes an i32 and returns an i32.

    For S = 35 the sums grow like this: 1, 5, 14, 30, 55. The sum for n = 4 is 30, which fits under 35, and adding 25 for n = 5 gives 55, which doesn't. So the answer is 4.

    Approach: keep adding until the next square doesn't fit

    The sums only grow as n grows, so the answer is the point where the next addition would cross S. That suggests a simulation: keep a running total, try the next square, and stop just before it would push the total past S.

    The number of iterations is the answer itself, and the sum of the first n squares is about n³ / 3, so n is roughly the cube root of 3 * S. The loop stays short even for very large S.

    Step by step

    1. Declare totalSoFar with let mut and start it at 0. Nothing has been added yet, and mut is needed because the value changes.
    2. Declare number with let mut and start it at 1, the first square to add.
    3. Write the while condition. It asks whether adding number * number to the total still leaves a value at most S. Looking one square ahead means the total itself never exceeds S.
    4. Add the square to totalSoFar with += inside the loop.
    5. Increase number by 1. Rust has no ++ operator, so use number += 1. Without this line the condition would never change and the loop would never end.
    6. Return number - 1. When the loop stops, number has already moved on to the first square that did not fit, so the answer is the number before it.

    Tracing S = 35: the loop adds 1, 4, 9 and 16 and number becomes 5. The check at 5 computes 30 + 25 = 55, which is more than 35, so the loop ends and the function returns 4.

    The solution in Rust

    impl Solution {
    fn find_largest_number(S: i32) -> i32 {
        let mut totalSoFar = 0;
        let mut number = 1;
        while totalSoFar + number * number <= S {
            totalSoFar += number * number;
            number += 1;
        }
        return number - 1;
    }
}

    Rust details worth knowing:

    • Inferred types. Neither variable has a type annotation. Both are compared with or added to S, which is an i32, so the compiler makes them i32 as well.
    • Naming. The names S and totalSoFar come from the lesson. Rust style prefers snake case such as s and total_so_far, and the compiler prints a warning about it. The code still builds and runs.
    • The loop condition is a plain expression. Unlike C-family languages, Rust takes no parentheses around the while condition, and the condition must be a bool; a number is never treated as true or false.
    • Compound assignment. += changes the variable in place, which is why both variables need mut.

    Complexity

    Time: O(S^(1/3)). Each iteration adds one square, and the loop runs once per term that fits. Since the sum of the first n squares is about n³ / 3, the number of iterations grows with the cube root of S. For S = 1,000,000 the answer is 143, so the loop runs 143 times.

    Space: O(1). Two integers, no matter how large S is.

    Edge cases and common mistakes

    • Exactly on the limit. For S = 30 the answer is 4, because the condition uses <=. With < the function would return 3.
    • Just under a sum. For S = 29 the answer is 3.
    • Small values. S = 1 returns 1. S = 0 returns 0, since even 1 doesn't fit and the loop never runs.
    • Checking after adding. A loop that adds the square first and tests afterwards overshoots by one term, so the result would be off by one.
    • Returning number instead of number - 1. The counter is always one past the answer when the loop ends.
    • Overflow with very large S. The lessons build Rust with optimizations, where i32 arithmetic wraps silently on overflow; a debug build would panic instead. The sum for n = 1860 is 2,146,682,110, and the next addition, of 3,463,321, goes past the largest i32, 2,147,483,647. When S is at least 2,146,682,110, the wrapped sum becomes a negative number, which passes the test <= S, and the loop keeps going. With S = 2147000000 this version returns 8548 instead of 1860. Doing the arithmetic in i64 avoids the problem:
    fn find_largest_number(s: i32) -> i32 {
    let s = s as i64;
    let mut total_so_far: i64 = 0;
    let mut number: i64 = 1;
    while total_so_far + number * number <= s {
        total_so_far += number * number;
        number += 1;
    }
    (number - 1) as i32
}

    This version returns 1860 for S = 2147000000 and for S = 2147483647. Inputs of that size are far beyond the lesson's examples, but the same loop on a smaller integer type would run into the problem much sooner.

    Testing

    • S = 35 gives 4.
    • S = 30 gives 4.
    • S = 29 gives 3.
    • S = 55 gives 5.
    • S = 100 gives 6.
    • S = 1 gives 1.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free