Start learning free

LESSON 141 OF 409 · LOOPS & GLOBAL VARIABLES

Student Grades - C++ Solution with O(n) Time Complexity

Practice Read the full explanation

Given the grades of a student as a vector, 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
    Ctrl + Enter to check

    C++ · LOOPS & GLOBAL VARIABLES

    Student Grades in C++, explained

    Understanding the Problem

    The core challenge of this problem is to determine if the average of the grades in the array is at least 5. This is a common problem in educational settings where a minimum average grade is required to pass a course.

    Potential pitfalls include incorrectly calculating the sum or average, or not handling edge cases such as an empty array.

    Approach

    To solve this problem, we can break it down into three main steps:

    1. Compute the sum of the grades.
    2. Compute the average by dividing the sum by the number of grades.
    3. Check if the average is greater than or equal to 5.

    Let's start with a naive approach and then optimize it.

    Naive Approach

    The naive approach involves iterating through the array to compute the sum, then dividing by the number of elements to get the average. This approach is straightforward but can be optimized for readability and efficiency.

    Optimized Approach

    The optimized approach is similar to the naive approach but ensures that the code is clean and efficient. We will use a single loop to compute the sum and then calculate the average.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Initialize a variable sum to 0.
    2. Iterate through each grade in the array and add it to sum.
    3. Compute the average by dividing sum by the number of grades.
    4. Return true if the average is greater than or equal to 5, otherwise return false.

    Code Implementation

    
#include <iostream>
#include <vector>

bool hasPassed(const std::vector<int>& grades) {
    // Step 1: Compute the sum of the grades
    int sum = 0;
    for (int grade : grades) {
        sum += grade;
    }

    // Step 2: Compute the average
    double average = static_cast<double>(sum) / grades.size();

    // Step 3: Check if the average is greater than or equal to 5
    return average >= 5;
}

int main() {
    std::vector<int> grades1 = {4, 7, 5, 9, 8, 2};
    std::vector<int> grades2 = {4, 7, 5, 3, 8, 2};

    std::cout << std::boolalpha;
    std::cout << "Student 1 passed: " << hasPassed(grades1) << std::endl;
    std::cout << "Student 2 passed: " << hasPassed(grades2) << std::endl;

    return 0;
}

    Complexity Analysis

    The time complexity of this approach is O(n), where n is the number of grades. This is because we iterate through the array once to compute the sum.

    The space complexity is O(1) as we only use a few extra variables (sum and average).

    Edge Cases

    Potential edge cases include:

    • An empty array: This should be handled by checking if the array is empty before computing the average.
    • All grades being the same: This should be handled correctly by the algorithm.

    Testing

    To test the solution comprehensively, we should include a variety of test cases:

    • Normal cases with mixed grades.
    • Edge cases such as an empty array.
    • Cases where all grades are the same.

    Thinking and Problem-Solving Tips

    When approaching such problems, it's important to break down the problem into smaller steps and solve each step methodically. Practice solving similar problems and studying algorithms to improve problem-solving skills.

    Conclusion

    In this blog post, we discussed how to determine if a student has passed based on their grades. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills.

    Additional Resources

    For further reading and practice problems, consider the following resources:

    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