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.
- If (Student doesn’t exists in Map)
- 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)); |
99
Time Complexity: O(N)
Auxiliary Space: O(N), As Map is used.
Contact Us