Divide Players Into Teams of Equal Skill - Practice Coding Problems

Divide Players Into Teams of Equal Skill - Problem

You are given a positive integer array skill of even length n where skill[i] denotes the skill of the i^th 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.

Input & Output

Example 1 — Basic Valid Case

$ Input: skill = [3,2,5,1,3,4]

› Output: 22

💡 Note: Sort to [1,2,3,3,4,5]. Pair from ends: (1,5) sum=6 chemistry=5, (2,4) sum=6 chemistry=8, (3,3) sum=6 chemistry=9. Total: 5+8+9=22

Example 2 — Impossible Case

$ Input: skill = [3,4]

› Output: 12

💡 Note: Only one possible pairing: (3,4). Team sum=7, chemistry=3×4=12. Since there's only one team, all teams have equal sums.

Example 3 — Cannot Form Equal Teams

$ Input: skill = [1,1,2,3]

› Output: -1

💡 Note: Sort to [1,1,2,3]. Try pairing from ends: (1,3) sum=4, (1,2) sum=3. Team sums are not equal, so return -1.

Constraints

2 ≤ skill.length ≤ 10⁵
skill.length is even
1 ≤ skill[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of player skills: [3,2,5,1,3,4]

Process

Sort and pair optimally: (1,5), (2,4), (3,3)

Output

Sum of team chemistry: 5+8+9=22

Key Takeaway

🎯 Key Insight: Sorting enables optimal pairing from opposite ends - this guarantees equal team sums if mathematically possible

Asked in

M Meta 15 a Amazon 12 G Google 8

The key insight is that after sorting, pairing players from opposite ends (weakest with strongest) guarantees equal team sums if a solution exists. The optimal approach sorts the array and uses two pointers, achieving O(n log n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Map Validation	O(n log n)	O(n)	Use frequency counting to validate if equal team formation is mathematically possible
Sort and Two Pointers	O(n log n)	O(1)	Sort players by skill, then pair from opposite ends to ensure equal team totals
Brute Force - Try All Pairings	O(n! / (2^(n/2) × (n/2)!))	O(n)	Generate all possible team pairings and check if any configuration has equal team totals

Frequency Map Validation — Algorithm Steps

Calculate total sum and target team sum
Count frequency of each skill level
Check if frequencies allow valid pairing
If valid, use two-pointer pairing to calculate chemistry

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count occurrence of each skill level

Check Complements

Verify each skill has matching complement count

Calculate Result

If valid, compute chemistry sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

long long solution(int* skill, int n) {
    if (n % 2 != 0) return -1;
    
    long long totalSum = 0;
    for (int i = 0; i < n; i++) {
        totalSum += skill[i];
    }
    
    int numTeams = n / 2;
    if (totalSum % numTeams != 0) {
        return -1;
    }
    
    long long targetSum = totalSum / numTeams;
    
    // Simple validation - sort and use two pointer approach
    qsort(skill, n, sizeof(int), compare);
    
    int left = 0, right = n - 1;
    while (left < right) {
        if (skill[left] + skill[right] != targetSum) {
            return -1;
        }
        left++;
        right--;
    }
    
    // Calculate chemistry
    long long chemistrySum = 0;
    left = 0;
    right = n - 1;
    
    while (left < right) {
        chemistrySum += (long long)skill[left] * skill[right];
        left++;
        right--;
    }
    
    return chemistrySum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int skill[1000];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        skill[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long result = solution(skill, n);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Frequency counting is O(n), but sorting for pairing is O(n log n)

⚡ Linearithmic

Space Complexity

O(n)

Hash map stores frequency count for each unique skill value

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Map Validation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler