2491. Divide Players Into Teams of Equal Skill

Description

The problem is about dividing players into pairs based on their skill levels. Each pair should have the same total skill value, and the task is to maximize the product of the skills in each pair. If it's not possible to divide them this way, return -1.

Intuition

We can sort the array and pair the smallest and largest elements, as these will have the most balanced skill differences. By checking if all such pairs have the same total skill, we can ensure an equal division. If the sum of a pair is different from others, it's impossible to divide players as required.

Approach

1. Sort the skill array.
2. Pair the smallest and largest elements iteratively.
3. Check if each pair sums up to the same total skill.
4. If they don't match, return -1.
5. Otherwise, compute the product of the paired skills and return the sum of all products.

Complexity

• Time Complexity: O(n log n) due to sorting the array.
• Space Complexity: O(1) as we're working in-place with the array.

Code

C++

class Solution {
public:
    long long dividePlayers(vector& skill) {
        sort(skill.begin(), skill.end());
        long long total = 0;
        long long targetSum = skill[0] + skill[skill.size() - 1];

        for (int i = 0, j = skill.size() - 1; i < j; ++i, --j) {
            if (skill[i] + skill[j] != targetSum) {
                return -1;
            }
            total += static_cast(skill[i]) *
                     skill[j]; // Use long long for multiplication
        }
        return total;
    }
};

Python

class Solution:
    def dividePlayers(self, skill):
        skill.sort()
        arr = []
        totalSum = skill[0] + skill[-1]

        for i in range(len(skill) // 2):
            if skill[i] + skill[-1 - i] != totalSum:
                return -1
            arr.append((skill[i], skill[-1 - i]))

        total = 0
        for x, y in arr:
            total += x * y
        return total

Java

class Solution {
    public long dividePlayers(int[] skill) {
        Arrays.sort(skill);
        long totalSum = skill[0] + skill[skill.length - 1];
        long total = 0;

        for (int i = 0, j = skill.length - 1; i < skill.length / 2; i++, j--) {
            if (skill[i] + skill[j] != totalSum) {
                return -1;
            }
            total += (long) skill[i] * skill[j];  // Use long to avoid overflow
        }
        return total;
    }

    public static void main(String[] args) {
        int[] skill = {3, 6, 1, 8, 4};  // Adjust this to the test case you're using
        Solution solution = new Solution();
        System.out.println(solution.dividePlayers(skill));
    }
}

JavaScript

    var dividePlayers = function (skill) {
        skill = skill.sort((a, b) => a - b)
        let arr = [], sub = [], a = skill.length - 1, totals = skill[0] + skill[a]
        for (let i = 0; i < skill.length / 2; i++) {

            sub = [skill[i], skill[a]]
            if (skill[i] + skill[a] !== totals) return -1
            totals = skill[i] + skill[a]
            arr.push(sub)
            a--


        }
        console.log(arr)
        let total = 0
        for (let i = 0; i < arr.length; i++) {
            total += arr[i][0] * arr[i][1]
        }
        return total
    };