2491. Divide Players Into Teams of Equal Skill
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.
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 <= 105skill.lengthis even.1 <= skill[i] <= 1000
Solutions
Solution 1: Sorting
To make all 2-person teams have equal skill points, the minimum value must match the maximum value. Therefore, we sort the skill array, and then use two pointers $i$ and $j$ to point to the beginning and end of the array respectively, match them in pairs, and judge whether their sum is the same number.
If not, it means that the skill points cannot be equal, and we directly return $-1$. Otherwise, we add the chemical reaction to the answer.
At the end of the traversal, we return the answer.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Where $n$ is the length of the skill array.
Python3
class Solution:
def dividePlayers(self, skill: List[int]) -> int:
skill.sort()
t = skill[0] + skill[-1]
i, j = 0, len(skill) - 1
ans = 0
while i < j:
if skill[i] + skill[j] != t:
return -1
ans += skill[i] * skill[j]
i, j = i + 1, j - 1
return ans
Java
class Solution {
public long dividePlayers(int[] skill) {
Arrays.sort(skill);
int n = skill.length;
int t = skill[0] + skill[n - 1];
long ans = 0;
for (int i = 0, j = n - 1; i < j; ++i, --j) {
if (skill[i] + skill[j] != t) {
return -1;
}
ans += (long) skill[i] * skill[j];
}
return ans;
}
}
C++
class Solution {
public:
long long dividePlayers(vector<int>& skill) {
sort(skill.begin(), skill.end());
int n = skill.size();
int t = skill[0] + skill[n - 1];
long long ans = 0;
for (int i = 0, j = n - 1; i < j; ++i, --j) {
if (skill[i] + skill[j] != t) return -1;
ans += 1ll * skill[i] * skill[j];
}
return ans;
}
};
Go
func dividePlayers(skill []int) (ans int64) {
sort.Ints(skill)
n := len(skill)
t := skill[0] + skill[n-1]
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
if skill[i]+skill[j] != t {
return -1
}
ans += int64(skill[i] * skill[j])
}
return
}
TypeScript
function dividePlayers(skill: number[]): number {
const n = skill.length;
skill.sort((a, b) => a - b);
const target = skill[0] + skill[n - 1];
let ans = 0;
for (let i = 0; i < n >> 1; i++) {
if (target !== skill[i] + skill[n - 1 - i]) {
return -1;
}
ans += skill[i] * skill[n - 1 - i];
}
return ans;
}
Rust
impl Solution {
pub fn divide_players(mut skill: Vec<i32>) -> i64 {
let n = skill.len();
skill.sort();
let target = skill[0] + skill[n - 1];
let mut ans = 0;
for i in 0..n >> 1 {
if skill[i] + skill[n - 1 - i] != target {
return -1;
}
ans += (skill[i] * skill[n - 1 - i]) as i64;
}
ans
}
}
JavaScript
var dividePlayers = function (skill) {
const n = skill.length,
m = n / 2;
skill.sort((a, b) => a - b);
const sum = skill[0] + skill[n - 1];
let ans = 0;
for (let i = 0; i < m; i++) {
const x = skill[i],
y = skill[n - 1 - i];
if (x + y != sum) return -1;
ans += x * y;
}
return ans;
};
Solution 2: Counting
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the skill array.
Python3
class Solution:
def dividePlayers(self, skill: List[int]) -> int:
s = sum(skill)
m = len(skill) >> 1
if s % m:
return -1
t = s // m
d = defaultdict(int)
ans = 0
for v in skill:
if d[t - v]:
ans += v * (t - v)
m -= 1
d[t - v] -= 1
else:
d[v] += 1
return -1 if m else ans
Java
class Solution {
public long dividePlayers(int[] skill) {
int s = Arrays.stream(skill).sum();
int m = skill.length >> 1;
if (s % m != 0) {
return -1;
}
int t = s / m;
int[] d = new int[1010];
long ans = 0;
for (int v : skill) {
if (d[t - v] > 0) {
ans += (long) v * (t - v);
--d[t - v];
--m;
} else {
++d[v];
}
}
return m == 0 ? ans : -1;
}
}
C++
class Solution {
public:
long long dividePlayers(vector<int>& skill) {
int s = accumulate(skill.begin(), skill.end(), 0);
int m = skill.size() / 2;
if (s % m) return -1;
int t = s / m;
int d[1010] = {0};
long long ans = 0;
for (int& v : skill) {
if (d[t - v]) {
ans += 1ll * v * (t - v);
--d[t - v];
--m;
} else {
++d[v];
}
}
return m == 0 ? ans : -1;
}
};
Go
func dividePlayers(skill []int) int64 {
s := 0
for _, v := range skill {
s += v
}
m := len(skill) >> 1
if s%m != 0 {
return -1
}
t := s / m
d := [1010]int{}
ans := 0
for _, v := range skill {
if d[t-v] > 0 {
ans += v * (t - v)
d[t-v]--
m--
} else {
d[v]++
}
}
if m == 0 {
return int64(ans)
}
return -1
}
TypeScript
function dividePlayers(skill: number[]): number {
let [sum, res, map] = [0, 0, new Map<number, number>()];
for (const x of skill) {
sum += x;
map.set(x, (map.get(x) || 0) + 1);
}
sum /= skill.length / 2;
for (let [x, c] of map) {
const complement = sum - x;
if ((map.get(complement) ?? 0) !== c) return -1;
if (x === complement) c /= 2;
res += x * complement * c;
map.delete(x);
map.delete(complement);
}
return res;
}
JavaScript
function dividePlayers(skill) {
let [sum, res, map] = [0, 0, new Map()];
for (const x of skill) {
sum += x;
map.set(x, (map.get(x) || 0) + 1);
}
sum /= skill.length / 2;
for (let [x, c] of map) {
const complement = sum - x;
if ((map.get(complement) ?? 0) !== c) return -1;
if (x === complement) c /= 2;
res += x * complement * c;
map.delete(x);
map.delete(complement);
}
return res;
}