Divide Players Into Teams of Equal Skill

Leetcode Problem:

• Divide Players Into Teams of Equal Skill

Summary

• Divide players into teams of equal skill and return the sum of chemistry of all teams.

Approach

• Use a hash map to store the frequency of each skill, sort the skills, and then iterate over the sorted skills to divide the players into teams.

Complexity

• O(n log n) due to sorting, where n is the number of players

Explain

• The solution first calculates the total skill and the target skill for each team
• It then iterates over the sorted skills, and for each skill, it checks if there is a corresponding team with the required skill
• If found, the players are divided into the team and the chemistry is calculated and added to the result
• If not found, the function returns -1.

Solution Code:

class Solution {
public:
    long long dividePlayers(vector& skill) {
        unordered_map m;
        sort(skill.begin(), skill.end());
        int total = 0;
        int N = skill.size();
        for(int i = 0 ; i < N; i++){
            m[skill[i]]++;
            total += skill[i];
        }
        int eachSum = total / (N / 2);
        long long res = 0;
        for(int i = 0 ; i < N/2; i++){
            int a = skill[i];
            int b = eachSum - a;
            if (m[a] == 0) return -1;
            m[a]--;
            if (m[b] == 0) return -1;
            m[b]--;
            res += a*b;
        }
        return res;

    }
};