Horje
Find Maximum Average Marks in Student Pairs

Given an array A[] containing N pairs in the form of (X, Y). Where X and Y denote the student’s name and marks respectively. Then your task is to output the maximum average marks of a student.

Examples:

Input: A[] = {{“Bob”, “87”}, {“Mike”, “35”}, {“Bob”, “52”}, {“Jason”, “35”}, {“Mike”, “55”}, {“Jessica”, “99”}}
Output: 99
Explanation: The average marks of each student are as follows:

  • Bob: (87+52)/2 = 139/2 = 69
  • Mike: (35+55)/2 = 90/2 = 45
  • Jason: (35/1) = 35
  • Jessica: (99/1) = 99

Input: A[] = {{“Pradeep”, “54”}, { “Neeraj”, “67”}, { “Sheetal”, “34”}}
Output: 67
Explanation: It can be verified that the maximum average marks will be 67.

Approach: To solve the problem follow the below idea:

The problem is implementation based and can be solved using HashMap Data-Structure. Store the total marks obtained by each student in a map along with occurrence of that student in A[]. Then the maximum average marks for each student can be calculated using the formula (Total_Marks/ Occurence of student in A[]). Then iterate map to find maximum average marks.

Steps were taken to solve the problem:

  • Create a variable let say MaxAvg and initialize it with Int_MIN intially.
  • Create an unorder HashMap let say Map.
  • Iterate over A[] using loop and follow below-mentioned steps under the scope of loop:
    • If (Student doesn’t exists in Map)
      • Initialize Key of Map as student’s name and Value as Pair of <Total_Marks, Occurence of student in A>
    • Else
      • Add marks of current student into stored Pair’s total marks and increment the occurrence.
  • Iterate over Map using loop and follow below-mentioned steps:
    • Average = (Student’s total marks/ Occurrence of student)
    • Update MaxAvg with max of (MaxAvg, Average)
  • Return MaxAvg.

Code to implement the approach:

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Method to return maximum average marks
int findMaxAverageMarks(vector<pair<string, string> >& A)
{
 
    // Variable to store the max avergae
    int maxAvg = INT_MIN;
 
    // If A is empty, then
    // returning 0 as max average
    if (A.empty())
        return 0;
 
    // Map to store name and Pair<Total Marks,
    // frequency of student name>
    unordered_map<string, pair<int, int> > Map;
 
    // Initializing map by iterating over A
    for (auto& current_student : A) {
 
        // name of student
        string studentName = current_student.first;
 
        // Marks of student
        int marks = stoi(current_student.second);
 
        // Storing name and total marks of student
        // using pair
        if (Map.find(studentName) == Map.end()) {
            Map[studentName] = make_pair(0, 0);
        }
 
        Map[studentName].first += marks;
        Map[studentName].second += 1;
    }
 
    // Loop for Iterating over map
    for (const auto& entry : Map) {
 
        // total marks
        double totalScore = entry.second.first;
 
        // Number of times student appeared in A
        int count = entry.second.second;
 
        // Updating maxAvg if avergare(total/count) is
        // greater than maxAvg
        maxAvg = max(maxAvg, (int)(totalScore / count));
    }
 
    // Returning the max average
    return maxAvg;
}
 
// Driver Function
int main()
{
    // Input
    vector<pair<string, string> > A
        = { { "Bob", "87" }, { "Mike", "35" },
            { "Bob", "52" }, { "Jason", "35" },
            { "Mike", "55" }, { "Jessica", "99" } };
 
    // Function Call
    cout << findMaxAverageMarks(A) << endl;
 
    return 0;
}

Java

// Java program for the above approach
import java.util.HashMap;
import java.util.Map;
 
public class GFG {
 
    // Method to return maximum average marks
    static int findMaxAverageMarks(Map<String, String>[] A)
    {
 
        // Variable to store the max average
        int maxAvg = Integer.MIN_VALUE;
 
        // If A is empty, then
        // returning 0 as max average
        if (A.length == 0)
            return 0;
 
        // Map to store name and Pair<Total Marks,
        // frequency of student name>
        Map<String, Pair<Integer, Integer> > map
            = new HashMap<>();
 
        // Initializing map by iterating over A
        for (Map<String, String> currentStudent : A) {
 
            // name of student
            String studentName
                = currentStudent.get("first");
 
            // Marks of student
            int marks = Integer.parseInt(
                currentStudent.get("second"));
 
            // Storing name and total marks of student
            // using pair
            if (!map.containsKey(studentName)) {
                map.put(studentName, new Pair<>(0, 0));
            }
 
            Pair<Integer, Integer> pair
                = map.get(studentName);
            pair.first += marks;
            pair.second += 1;
        }
 
        // Loop for Iterating over map
        for (Map.Entry<String, Pair<Integer, Integer> >
                 entry : map.entrySet()) {
 
            // total marks
            double totalScore = entry.getValue().first;
 
            // Number of times student appeared in A
            int count = entry.getValue().second;
 
            // Updating maxAvg if average(total/count) is
            // greater than maxAvg
            maxAvg = Math.max(maxAvg,
                              (int)(totalScore / count));
        }
 
        // Returning the max average
        return maxAvg;
    }
 
    // Driver Function
    public static void main(String[] args)
    {
 
        // Input
        Map<String, String>[] A = new Map[] {
            Map.of("first", "Bob", "second", "87"),
            Map.of("first", "Mike", "second", "35"),
            Map.of("first", "Bob", "second", "52"),
            Map.of("first", "Jason", "second", "35"),
            Map.of("first", "Mike", "second", "55"),
            Map.of("first", "Jessica", "second", "99")
        };
 
        // Function Call
        System.out.println(findMaxAverageMarks(A));
    }
 
    // Custom Pair class to store two values
    static class Pair<A, B> {
        A first;
        B second;
 
        Pair(A first, B second)
        {
            this.first = first;
            this.second = second;
        }
    }
}
 
// This code is contributed by Susobhan Akhuli

Python3

# Python program for the above approach
 
# Method to return maximum average marks
def find_max_average_marks(A):
    # Variable to store the max average
    max_avg = float('-inf')
 
    # If A is empty, then
    # returning 0 as max average
    if not A:
        return 0
 
    # Dictionary to store name and Tuple(Total Marks, frequency of student name)
    student_map = {}
 
    # Initializing dictionary by iterating over A
    for current_student in A:
        # name of student
        student_name = current_student[0]
 
        # Marks of student
        marks = int(current_student[1])
 
        # Storing name and total marks of student
        # using Tuple
        if student_name not in student_map:
            student_map[student_name] = (0, 0)
 
        total_marks, count = student_map[student_name]
        student_map[student_name] = (total_marks + marks, count + 1)
 
    # Loop for iterating over dictionary
    for student, (total_score, count) in student_map.items():
        # Updating max_avg if average(total/count) is
        # greater than max_avg
        max_avg = max(max_avg, total_score / count)
 
    # Returning the max average
    return int(max_avg)
 
# Driver Function
if __name__ == "__main__":
    # Input
    A = [
        ("Bob", "87"), ("Mike", "35"),
        ("Bob", "52"), ("Jason", "35"),
        ("Mike", "55"), ("Jessica", "99")
    ]
 
    # Function Call
    print(find_max_average_marks(A))
 
# This code is contributed by Susobhan Akhuli

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
    // Method to return maximum average marks
    static int
    FindMaxAverageMarks(List<Tuple<string, string> > A)
    {
        // Variable to store the max average
        int maxAvg = int.MinValue;
 
        // If A is empty, then returning 0 as max average
        if (A.Count == 0)
            return 0;
 
        // Dictionary to store name and Tuple(Total Marks,
        // frequency of student name)
        Dictionary<string, Tuple<int, int> > Map
            = new Dictionary<string, Tuple<int, int> >();
 
        // Initializing map by iterating over A
        foreach(var current_student in A)
        {
            // Name of student
            string studentName = current_student.Item1;
 
            // Marks of student
            int marks = int.Parse(current_student.Item2);
 
            // Storing name and total marks of student using
            // Tuple
            if (!Map.ContainsKey(studentName))
                Map[studentName] = Tuple.Create(0, 0);
 
            Tuple<int, int> tuple = Map[studentName];
            Map[studentName] = Tuple.Create(
                tuple.Item1 + marks, tuple.Item2 + 1);
        }
 
        // Loop for Iterating over map
        foreach(var entry in Map)
        {
            // Total marks
            double totalScore = entry.Value.Item1;
 
            // Number of times student appeared in A
            int count = entry.Value.Item2;
 
            // Updating maxAvg if average(total/count) is
            // greater than maxAvg
            maxAvg = Math.Max(maxAvg,
                              (int)(totalScore / count));
        }
 
        // Returning the max average
        return maxAvg;
    }
 
    // Driver Function
    public static void Main(string[] args)
    {
        // Input
        List<Tuple<string, string> > A
            = new List<Tuple<string, string> >{
                  Tuple.Create("Bob", "87"),
                  Tuple.Create("Mike", "35"),
                  Tuple.Create("Bob", "52"),
                  Tuple.Create("Jason", "35"),
                  Tuple.Create("Mike", "55"),
                  Tuple.Create("Jessica", "99")
              };
 
        // Function Call
        Console.WriteLine(FindMaxAverageMarks(A));
    }
}
 
// This code is contributed by Susobhan Akhuli

Javascript

// javaScript code for the above approach
 
// Method to return maximum average marks
function findMaxAverageMarks(A) {
    // Variable to store the max average
    let maxAvg = -Infinity;
 
    // If A is empty, then return 0 as max average
    if (A.length === 0) {
        return 0;
    }
 
    // Map to store name and Pair<Total Marks,
    // frequency of student name>
    const marksMap = new Map();
 
    // Initializing map by iterating over A
    for (let i = 0; i < A.length; i++) {
        const [studentName, marks] = A[i];
 
        // Storing name and total marks of
        // student using pair
        if (!marksMap.has(studentName)) {
            marksMap.set(studentName, [0, 0]);
        }
 
        const [totalMarks, count] = marksMap.get(studentName);
        marksMap.set(studentName, [totalMarks + parseInt(marks), count + 1]);
    }
 
    // Loop for Iterating over map
    for (const [studentName, [totalMarks, count]] of marksMap.entries()) {
        // Updating maxAvg if average(total/count)
        // is greater than maxAvg
        maxAvg = Math.max(maxAvg, Math.floor(totalMarks / count));
    }
 
    // Returning the max average
    return maxAvg;
}
 
// Input
const A = [
    ["Bob", "87"],
    ["Mike", "35"],
    ["Bob", "52"],
    ["Jason", "35"],
    ["Mike", "55"],
    ["Jessica", "99"]
];
 
// Function Call
console.log(findMaxAverageMarks(A));

Output

99

Time Complexity: O(N)
Auxiliary Space: O(N), As Map is used.


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Maximize Array sum by replacing middle elements with min of Subarray corners Maximize Array sum by replacing middle elements with min of Subarray corners
How Array is stored in different programming languages? How Array is stored in different programming languages?
Dynamic Programming (DP) on Arrays Tutorial Dynamic Programming (DP) on Arrays Tutorial
Min Operations for Target Sum in Special Sequence Min Operations for Target Sum in Special Sequence
Task Allocation to Game Slots Task Allocation to Game Slots

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje