• Posts

Problem 2491 Divide Players Into Teams of Equal Skill

Problem Statement

Link - Problem 2491

Question

You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n / 2 teams of size 2 such that the total skill of each team is equal.

The chemistry of a team is equal to the product of the skills of the players on that team.

Return the sum of the chemistry of all the teams, or return -1 if there is no way to divide the players into teams such that the total skill of each team is equal.

Example 1:

Input: skill = [3,2,5,1,3,4]
Output: 22
Explanation: 
Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6.
The sum of the chemistry of all the teams is: 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9 = 22.

Example 2:

Input: skill = [3,4]
Output: 12
Explanation: 
The two players form a team with a total skill of 7.
The chemistry of the team is 3 * 4 = 12.

Example 3:

Input: skill = [1,1,2,3]
Output: -1
Explanation: 
There is no way to divide the players into teams such that the total skill of each team is equal.

Constraints:

• 2 <= skill.length <= 105
• skill.length is even.
• 1 <= skill[i] <= 1000

Solution

class Solution {
public:
    long long dividePlayers(vector<int>& skill) {
        sort(skill.begin(), skill.end());

        int n = skill.size();
        long long res = 0;
        int target = skill[0] + skill[n - 1];

        for (int i = 0; i < n / 2; i++) {
            int curr = skill[i] + skill[n - i - 1];

            if (curr != target) {
                return -1;
            }

            res += (long long)skill[i] * (long long)skill[n - i - 1];
        }

        return res;
    }
};

Complexity Analysis

| Algorithm                                   | Time Complexity | Space Complexity |
| ------------------------------------------- | --------------- | ---------------- |
| Modified Two-Pointer Technique with Sorting | O(n log n)      | O(1)             |

Explanation

Intial Thoughts

To approach this problem, we first need to consider how to divide the players into teams of two with equal total skills. We can start by thinking about how to pair the players in a way that each pair has the same total skill. One possible way is to sort the skills in ascending order and then pair the players from the start and end of the sorted list. This way, we can ensure that each pair has the same total skill. We also need to consider how to calculate the chemistry of each team, which is the product of the skills of the players on that team.

Intuitive Analysis

The key to solving this problem is to realize that we need to find a way to pair the players such that each pair has the same total skill. By sorting the skills in ascending order, we can pair the players from the start and end of the list, ensuring that each pair has the same total skill. We can then calculate the chemistry of each team by multiplying the skills of the players on that team. If at any point we find a pair with a different total skill, we can immediately return -1, as it is not possible to divide the players into teams with equal total skills. By following this approach, we can intuitively solve the problem and find the sum of the chemistry of all the teams.

1. Intuition

• The problem requires dividing players into teams of size 2 with equal total skill, so we need to find pairs of players with complementary skills.
• To find these pairs efficiently, we can sort the skills in ascending order and then pair the smallest skill with the largest, the second smallest with the second largest, and so on.
• This approach ensures that each team has the same total skill, which is the sum of the smallest and largest skills.
• If at any point the sum of the current pair’s skills does not match the target sum, we can immediately return -1, as it’s impossible to divide the players into teams with equal total skill.
• The key insight here is that the total skill of each team must be the same, and by sorting the skills, we can easily find pairs that satisfy this condition.
• This solution works because it takes advantage of the fact that the skills are sorted, allowing us to efficiently find pairs with complementary skills.
• The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of players.

2. Implementation

• We start by sorting the skill vector in ascending order using the sort function.
• We then calculate the target sum by adding the smallest and largest skills, which is stored in the target variable.
• We iterate over the sorted skill vector, pairing the smallest skill with the largest, the second smallest with the second largest, and so on, using a for loop that runs n / 2 times.
• Inside the loop, we check if the sum of the current pair’s skills matches the target sum, and if not, we immediately return -1.
• If the sum matches, we add the product of the current pair’s skills to the res variable, which stores the sum of the chemistry of all teams.
• Finally, we return the res variable, which contains the sum of the chemistry of all teams, or -1 if it’s impossible to divide the players into teams with equal total skill.
• The res variable is declared as a long long to avoid overflow when calculating the sum of the chemistry of all teams.

Complexity Analysis

Time Complexity:

• The time complexity is driven by the sort(skill.begin(), skill.end()) operation which takes O(n log n) time due to the use of a comparison-based sorting algorithm, where n is the number of elements in the input array skill.
• The subsequent for loop iterates over the sorted array, performing a constant amount of work for each element, resulting in a time complexity of O(n). However, this is dominated by the O(n log n) time complexity of the sorting operation.
• Therefore, the overall time complexity is O(n log n) due to the sorting operation, where the n log n term represents the worst-case, average-case, and best-case time complexity.

Space Complexity:

• The space complexity is determined by the additional memory used by the algorithm, which in this case is constant since we are not using any data structures that scale with the input size.
• The use of a few extra variables such as n, res, and target does not affect the space complexity since they do not grow with the input size.
• The sorting operation sort(skill.begin(), skill.end()) is performed in-place, meaning it does not require any extra space that scales with the input size, resulting in a space complexity of O(1).

Footnote

This question is rated as Medium difficulty.

Hints

Try sorting the skill array.

It is always optimal to pair the weakest available player with the strongest available player.

Similar Questions: