Divide Players Into Teams of Equal Skill

Problem Description

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.

Key Insights

• The sum of skills for each team must be the same.
• Pairing the highest skill with the lowest skill can help achieve equal sum teams.
• If not all pairs yield the same total skill, return -1.
• Chemistry can be computed as the product of the two skills in each pair.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the skill array.
Space Complexity: O(1) - no additional data structures are used that scale with input size.

Solution

To solve the problem, we can follow these steps:

1. Sort the skill array in ascending order.
2. Use two pointers: one starting from the beginning (low) and one from the end (high) of the sorted array.
3. Check if the sum of the skills at these two pointers (low and high) is constant across all pairs formed.
4. If the sums are equal, calculate the chemistry for each team by multiplying the skills at low and high, and accumulate this value. If any pair does not match the target sum, return -1.

Code Solutions