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& skill) { const int n = skill.size(); const int teamSkill = accumulate(skill.begin(), skill.end(), 0) / (n / 2); long long ans = 0; unordered_map 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(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 count = new HashMap<>(); for (final int s : skill) count.merge(s, 1, Integer::sum); for (Map.Entry 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