Skip to content

2491. Divide Players Into Teams of Equal Skill 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  long long dividePlayers(vector<int>& skill) {
    const int n = skill.size();
    const int teamSkill = accumulate(skill.begin(), skill.end(), 0) / (n / 2);
    long ans = 0;
    unordered_map<int, int> count;

    for (const int s : skill)
      ++count[s];

    for (const auto& [s, freq] : count) {
      const int requiredSkill = teamSkill - s;
      if (const auto it = count.find(requiredSkill);
          it == count.cend() || it->second != freq)
        return -1;
      ans += static_cast<long>(s) * requiredSkill * freq;
    }

    return ans / 2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public long dividePlayers(int[] skill) {
    final int n = skill.length;
    final int teamSkill = Arrays.stream(skill).sum() / (n / 2);
    long ans = 0;
    Map<Integer, Integer> count = new HashMap<>();

    for (final int s : skill)
      count.merge(s, 1, Integer::sum);

    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
      final int s = entry.getKey();
      final int freq = entry.getValue();
      final int requiredSkill = teamSkill - s;
      if (count.getOrDefault(requiredSkill, 0) != freq)
        return -1;
      ans += (long) s * requiredSkill * freq;
    }

    return ans / 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def dividePlayers(self, skill: list[int]) -> int:
    n = len(skill)
    teamSkill = sum(skill) // (n // 2)
    ans = 0
    count = collections.Counter(skill)

    for s, freq in count.items():
      requiredSkill = teamSkill - s
      if count[requiredSkill] != freq:
        return -1
      ans += s * requiredSkill * freq

    return ans // 2