Punish the Students

A Professor conducts a Computer Science paper for N students. He had strictly instructed all students to sit according to their roll numbers. However when he started checking the papers, he found out that all the papers were randomly ordered because the students had sat randomly during the exam instead of sitting according to their roll numbers. The order is given in list of integers roll[ ]. The professor became very angry and he wanted to teach the students a lesson.

He decided to sort the papers according to roll numbers by Bubble Sort and count the number of swaps required for each and every student and deduct as many marks of a student as were the number of swaps required for that student. The marks of every student is given in list of integers marks[ ] in the order in which they were sitting. However he also has to maintain the class average greater than or equal to a set minimum avg, else he may lose his job. The Professor wants to know whether he should punish the students or save his job.

• Time : O(n^2)
• Space : O(1)

class Solution {
public:
    int shouldPunish(int roll[], int marks[], int n, double avg) {
        int count = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n - i - 1; j++) {
                if(roll[j] > roll[j + 1]) {
                    swap(roll[j], roll[j+1]);
                    count++;
                }
            }
        }
    
        int sum = accumulate(marks, marks + n, 0);
        
        return 1.0 * (sum - count * 2) / n >= avg;
    }
};

• Time : O(nlogn)
• Space : O(n)

class Solution {
public:
    int shouldPunish(int roll[], int marks[], int n, double avg) {
        int count = 0, sum = accumulate(marks, marks + n, 0);
        unordered_map<int, int> mp;
        for(int i = 0; i < n; i++) {
            marks[i] = roll[i];
            mp[roll[i]] = i;
        }
        sort(marks, marks + n);
        for(int i = 0; i < n; i++) {
            count += abs(mp[marks[i]] - i);
        }
        
        return 1.0 * (sum - count) / n >= avg;
    }
};