Question

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 <= 105
• skill.length is 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.

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

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;
  }
}

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;
  }
};

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
}

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;
}

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
  }
}

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.

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

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;
  }
}

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;
  }
};

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
}