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

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

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

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:

• GeeksforGeeks
• LeetCode
• HackerRank