LESSON 149 OF 414 · LOOPS & GLOBAL VARIABLES

Student Grades in Rust: Average in O(n) Time and O(1) Space

Given the grades of a student as an array, determine if the student has passed the class.

A Student has passed the class if the average of grades is 5 or more.

The average is defined as (grades[0] + grades[1] + ... + grades[n - 1]) / n

Example 1:

Input: grades = [4, 7, 5, 9, 8, 2]
Output: true
Explanation:
average = (4 + 7 + 5 + 9 + 8 + 2) / 6 =
= 35 / 6 = 5.833333333... >= 5

Example 2:

Input: grades = [4, 7, 5, 3, 8, 2]
Output: false
Explanation:
average = (4 + 7 + 5 + 3 + 8 + 2) / 6 =
= 29 / 6 = 4.83333.. < 5

Hints:

The problem can be broken in 3 steps:
1. Compute the sum of the array
2. Compute the average by dividing the sum by the length of the array
3. Decide the result based on the average being greater than or equal to 5
Let's start with step 1: How can we compute the sum of the array?

First of all, we should store this sum somewhere as we compute it. That 'somewhere' is a variable, let's name it sum. We have to iterate through every element of grades and add its value to sum. How can we achieve this?

With a loop! Let's use a for loop and a variable grade to iterate through the elements:

sum = 0
for each grade in grades:
	sum += grade

When the loop terminates, we know the sum. What should we do next?

We should compute average = sum / length and return average >= 5:

sum = 0
for each grade in grades:
	sum += grade
average = sum / length
return average >= 5

We have a for loop that performs exactly n iterations (n is the length of grades), thus the Time Complexity is O(n).
The only extra space we use are the variables sum, average and the iterator variable grade inside the loop, thus the Extra Space used is O(1).

STEP 1 OF 5

Guided

Ctrl + Enter to check

Student Grades in Rust, explained

Problem overview

The function has_passed receives a vector of integer grades and returns true when their average is 5 or more. The average is the sum of the grades divided by how many there are.

For grades = [4, 7, 5, 9, 8, 2] the sum is 35 and there are 6 grades, so the average is 35 / 6, about 5.83. That is at least 5, so the result is true. For [4, 7, 5, 3, 8, 2] the sum is 29 and the average is about 4.83, so the result is false.

Approach

The problem splits into three small jobs:

add up all the grades;
divide the sum by the number of grades;
compare the average with 5.

The first job is the same accumulator pattern as any sum. A variable starts at zero, a loop visits each grade, and each pass adds the grade to the variable. The other two jobs take one line each. One pass over the vector with a few variables gives O(n) time and O(1) extra space.

Step by step

Declare the sum as an f32. let mut sum = 0.0f32; is a mutable floating-point variable. Making it a float means the later division keeps its fractional part, so the average is 5.83 and not a rounded 5.
Loop over a reference to the vector. for grade in &grades borrows the vector instead of moving it. That matters because the length is needed again after the loop.
Add each grade, converted. Looping over &grades gives a &i32 for each element. The * reads the number behind the reference, and as f32 converts it. Rust never mixes integer and float types in arithmetic on its own, so the cast is required.
Divide by the length. grades.len() is a usize, so it is also converted with as f32 before the division.
Compare with 5.0. The average is an f32, so the threshold is a float literal. Writing 5 would not compile against a float.

The solution in Rust

impl Solution {
    fn has_passed(grades: Vec<i32>) -> bool {
        let mut sum = 0.0f32;
        for grade in &grades {
            sum += *grade as f32;
        }
        let average = sum / grades.len() as f32;
        return average >= 5.0;
    }
}

Some Rust details here:

The 0.0f32 literal. The suffix sets the type of the literal. Without it, the compiler would work out the type from later use, and here it would still arrive at f32.
Precedence of as. In *grade as f32, the dereference happens first and then the cast. In grades.len() as f32, the method call comes first.
No implicit conversions. Adding an i32 to an f32, or dividing an f32 by a usize, is a compile error. Each value has to be converted by hand.
The comparison is the return value. average >= 5.0 already produces a bool, so no if is needed.
f32 precision. It holds about seven significant digits. For the sums in this lesson, that is plenty. The comparison to 5.0 is exact when the true average is exactly 5, such as for [5, 5, 5].

Complexity

Time: O(n). The loop makes one pass over the n grades, with constant work on each. Reading the length is O(1).

Space: O(1). The function stores sum, average and the loop variable, no matter how many grades there are.

Edge cases and common mistakes

Exactly 5. An average of 5 passes, because the comparison is >=. [5] and [5, 5, 5] both give true.
An empty vector. The sum is 0.0 and the length is 0, so the division is 0.0 / 0.0, which is NaN (not a number). Any comparison with NaN is false, so the function returns false and does not panic. An integer division by zero, by contrast, would panic.
Forgetting a cast. sum += grade; with a float sum and an &i32 does not compile. The same goes for dividing by grades.len() without the cast.
Cutting the average with integer division. In Rust, 35 / 6 is 5, because integers divide without a fraction. For this particular check, the answer still comes out right, since an average below 5 always truncates to 4 or less. The float version is still the better habit, because it keeps the real average if you ever need to print it.
Dividing by the wrong count. The divisor is the number of grades, not the largest grade or the last index.

Testing

[4, 7, 5, 9, 8, 2] gives true.
[4, 7, 5, 3, 8, 2] gives false.
[5] gives true.
[5, 5, 5] gives true.
[] gives false.

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

Start learning free