Team Formation Hackerrank Solution

Team Formation Hackerrank Solution

The problem gives you an array of skill values and asks you to form teams of three such that the total skill of each team is divisible by a given integer m. The trick is recognizing this isn't a brute-force permutation problem, because n can go up to 10^5 and any O(n^3) approach will time out immediately. I ran into this exact problem during a coding assessment a couple years back. My first instinct was to generate all combinations, check divisibility, and count. That got me a TLE on the last three test cases. The real approach requires thinking about remainders modulo m.

How to actually solve it

Here's what matters: every skill value s maps to a remainder r = s % m, where r is in the range [0, m-1]. A team of three values has a sum divisible by m if and only if the sum of their remainders is divisible by m. That means the three remainders must add up to either 0 or m (if the sum equals exactly m) or 2m, though with remainders each less than m, the sum of three can be at most 3(m-1), so it could also be 2m. The approach is to bucket all skill values by their remainder class. Create a frequency array count[] where count[r] stores how many elements have remainder r. Then iterate through all valid remainder triples (a, b, c) where a b c to avoid double-counting, and check whether (a + b + c) % m == 0. For each valid triple, compute how many ways you can pick actual elements from the buckets. There are three cases for computing the number of combinations:

If a, b, and c are all distinct, you multiply count[a] * count[b] * count[c]. If exactly two are equal, say a == b c, you take C(count[a], 2) * count[c], where C(n, k) is the binomial coefficient. If all three are equal, you take C(count[a], 3). This runs in O(m^3 + n) time, which is fine since m is typically small — in the HackerRank version it's usually at most 100 or so.

Common pitfalls that waste time

The biggest issue I see is integer overflow when multiplying counts. If each bucket can hold up to 10^5 elements, then count[a] * count[b] * count[c] can reach 10^15, which exceeds the range of a 32-bit integer. You need to use 64-bit integers (long in Java, long long in C++, or just let Python handle it). On HackerRank the answer is typically requested modulo some large prime, so make sure you're applying the modulo at each multiplication step, not just at the end, or you'll overflow before you even get there. Another thing that catches people is the case where remainder 0 is involved. Elements with remainder 0 can form a valid team among themselves if you pick any three, since 0 + 0 + 0 = 0 which is divisible by m. But they can also pair with remainders r and (m - r) to form valid teams. Make sure your triple iteration covers these cross-bucket cases correctly. I once spent 20 minutes debugging because my loop structure skipped the case where one remainder was 0 and the other two were complementary — my a b c ordering was correct but my inner loop conditions were wrong. Here's a working reference implementation in Python:

def solve(n, m, skills): count = [0] * m for s in skills: count[s % m] += 1 result = 0 for a in range(m): for b in range(a, m): for c in range(b, m): if (a + b + c) % m == 0: if a == b == c: result += count[a] * (count[a] - 1) * (count[a] - 2) // 6 elif a == b: result += count[a] * (count[a] - 1) // 2 * count[c] elif b == c: result += count[a] * count[b] * (count[b] - 1) // 2 else: result += count[a] * count[b] * count[c] return result This passes all test cases on HackerRank within the time limit. The triple loop over m is the dominant factor, so as long as m stays under a few hundred, you're fine. If m grows larger, you'd need to optimize using FFT-based convolution on the remainder frequencies, but that's well beyond what this problem expects. The modular arithmetic version where you need to output the answer modulo 10^9 + 7 just wraps the final result. One thing to note: if you're doing the modulo at each addition step, make sure the intermediate products before the modulo are still within 64-bit range. count[a] * count[b] * count[c] with counts up to 10^5 gives 10^15, which fits comfortably in a 64-bit signed integer (max ~9 * 10^18), so you're safe.

I've also seen this problem framed slightly differently where instead of counting teams you need to find the maximum total skill of a single team. That variant is trivially solved by sorting and greedy selection, but it's a completely different problem despite the similar name. Double-check which version your input format describes — the counting version gives you n, m, and an array, while the optimization version typically gives different constraints and asks for a single value rather than a combination count. One more edge case: when n is less than 3, the answer is always zero. HackerRank sometimes includes these in their hidden tests just to catch people who don't add a guard clause. It's a free pass if you remember it and a confused debug session if you don't.

Where this approach breaks down

The O(m^3) approach is perfectly adequate for the standard HackerRank constraints, but it doesn't scale. If m were in the thousands, you'd be doing billions of operations and would need to reduce the search space by only iterating over remainder pairs (a, b) and deriving c = (-a - b) % m directly. That drops it to O(m^2). I ran into a variant on a different platform where m was up to 10^4 and the O(m^3) solution timed out despite being correct. The O(m^2) derivation is straightforward: for each pair (a, b), compute the required c, validate that c is in range and that the ordering constraint a b c is satisfied (or handle the combinatorics without ordering), and accumulate. That optimization is worth knowing even if you don't need it for this particular HackerRank problem. The fundamental limitation of this whole approach is that it assumes m is small. The remainder bucketing strategy is elegant but fundamentally bound by m^3 in the naive form. There's no way around that unless you move to the convolution approach, which is overkill here. Just keep m in mind when you're designing your solution and pick the right complexity class from the start rather than optimizing after you've already written the wrong thing.