Divide Players Into Teams of Equal Skill
Asked at Visa
Problem
Divide Players Into Teams of Equal Skill asks you to pair up an even number of players so that every pair has the same total skill, and to return the sum of the products of each pair's skills (or -1 if impossible). Sorting shows the only possible pairing: smallest with largest.
Asked At
| Company | Difficulty | |
|---|---|---|
| Visa | Medium | View all Visa questions → |
How to Think About It
Every team must sum to total / (n / 2). If that is not an integer, the answer is -1.
Key insight: after sorting, the smallest player must pair with the largest (anyone else would give a different sum from the pairs that remain). So pair from both ends inward.
Check each pair sums to the same target; if any pair differs, return -1.
Accumulate the product skill[i] * skill[n-1-i] for each pair, using 64-bit arithmetic.
Walkthrough for [3,2,5,1,3,4]: sorted [1,2,3,3,4,5]; pairs (1,5), (2,4), (3,3) all sum to 6 -> 5 + 8 + 9 = 22.
Optimal Approach
Step 1: Sort skill.
Step 2: target = skill[0] + skill[-1], res = 0.
Step 3: For i in 0..n/2-1: if skill[i] + skill[n-1-i] != target, return -1; else res += skill[i] * skill[n-1-i].
Step 4: Return res.
Time: O(n log n) (or O(n) with counting since skills are small). Space: O(1) extra.
What Trips People Up in Real Interviews
Trying all pairings with backtracking — exponential and unnecessary.
Returning the common team sum instead of the sum of products.
32-bit overflow when summing up to 5 * 10^4 products of values up to 1000.
Not justifying why smallest-with-largest is forced.
Solution Code
def dividePlayers(skill):
skill.sort()
n = len(skill)
target = skill[0] + skill[-1]
res = 0
for i in range(n // 2):
a, b = skill[i], skill[n - 1 - i]
if a + b != target:
return -1
res += a * b
return resFrequently Asked Questions
What is the Divide Players Into Teams of Equal Skill problem?
Divide Players Into Teams of Equal Skill asks you to pair up an even number of players so that every pair has the same total skill, and to return the sum of the products of each pair's skills (or -1 if impossible). Sorting shows the only possible pairing: smallest with largest.
How do you solve Divide Players Into Teams of Equal Skill?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Divide Players Into Teams of Equal Skill?
Divide Players Into Teams of Equal Skill is asked at Visa. It is a medium difficulty problem.
What are common mistakes on Divide Players Into Teams of Equal Skill?
- Trying all pairings with backtracking — exponential and unnecessary.
- Returning the common team sum instead of the sum of products.
- 32-bit overflow when summing up to `5 * 10^4` products of values up to 1000.
- Not justifying why smallest-with-largest is forced.