Amazon Online Assessment 2021 (OA) - Max Subjects Number

In a game where quizzes are used to practice for big tests, each quiz focuses on one or more subjects. In each subject, only a certain number of answers are allowed. We're trying to find out how this limit affects the chances of students passing each subject.

Here's an example: Suppose answered[i] represents the number of questions already answered by the student in the ith subject. Let's say the student still has time to answer a total of q more questions in any subject. For each ith subject, the student must answer at least need[i] questions to pass. The challenge is to figure out the maximum number of subjects the student can pass if they spread their q additional answers across the subjects.

Let's paint a clearer picture: imagine there are n=2 subjects. To pass them, the student has to answer needed=[4,5] questions in each subject, respectively. The student has answered answered=[2,4] questions in these two subjects so far, and they are able to answer another q=1 question in total across both subjects. The smart choice would be to use this one extra question in the second subject. The first subject would still need two more answers to pass, so it makes more sense to aim for a pass in the second subject. That way, the student can pass a maximum of 1 subject.

Relevant Amazon OA Problems:

Input

answered: a size n array of integers
needed: a size n array of integers
q: an integer

Output

maximum number of subjects the student can pass

Examples

Example 1:

Input:

answered = [24, 27, 0]
needed = [51, 52, 100]
q = 100

Output: 2

Explanation:

Here answered=[24,27,0] and needed=[51,52,100]. The additional answers needed to pass are [27,25,100]. The best distribution is at least 27+25=52 questions among the first two subjects. It would take all q=100 questions to pass the third subject.

Example 2:

Input:

answered = [24, 27, 0]
needed = [51, 52, 200]
q = 100

Output: 3