[Solution]Problem 32: Maximize Average Pass Ratio[Goldman Sachs]
Math, Problem Solving, Linear Data Structures, Lists
I hope you’re ready for this one, we’re going to learn a lot in this solution.
Problem
There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes
, where classes[i] = [passi, totali]
. You know beforehand that in the ith
class, there are totali
total students, but only passi
number of students will pass the exam.
You are also given an integer extraStudents
. There are another extraStudents
brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents
students to a class in a way that maximizes the average pass ratio across all the classes.
The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.
Return the maximum possible average pass ratio after assigning the extraStudents
students. Answers within 10-5
of the actual answer will be accepted.
Example 1:
Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.
This question can be practiced as Leetcode 1792. Maximum Average Pass Ratio. Feel free to test your solution there
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below -
Step 1: Getting all the pieces on the board
All the consistent readers know that I stress this step a lot. Understanding the question, the data given, what is needed, and the constraints are crucial for solving the problems given to us. This step also helps make relevant steps and is a great way to show off your communication and problem-solving skills.
Getting to this question, what are the important things we care about-
Input- classes is a list with the shape [class0, class1 …class_n]. Each class member is further a list of size 2 shaped, [pass_i, total_i]. As we know the first represents how many students will pass, and the second represents the total population of the class. We also have an int giving us a bunch of students not affiliated to any class, that we want to add to meet our objective.
Objective- We want to maximize the average ratio of people passing. We achieve this by strategically allocating the extra genius students to the class they will impact the most.We can calculate the ratio for a class with class[0]/class[1]
Interesting point to note- As we add a genius to a class, the ratio changes. Thus we want to utilize a data structure that will allow for easy retrieval and insertion.
Doing this step might seem trivial, but trust me it has a lot of benefits. You will reduce the number of mistakes you make by following this approach, and this will give you a direction to move your solution into next. Looking at all we’ve been given and all we know, we can deduce that a reasonable next step would be to figure out which class we want to add our genius to.
The answer is actually really obvious. We will add the genius to the class that would be most impacted the most. Surprising I know.
So now we have another question? How do we figure out which class has the most to gain from adding a single genius? Once we can create a function to calculate this, we can just loop till we run out of geniuses.
It might seem like this process just shifted goalposts. However, that would be incorrect. Notice how we have significantly narrowed the scope of what our next step has to be. Our minds are not good at solving big, complex, ambiguous problems. It is, however, fantastic at solving specific well-defined problems. And we now have a very useful subproblem to solve. How do we define gain?
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.