Split Array With Same Average

Split Array With Same Average

What is this problem about?

In the Split Array With Same Average coding problem, you are given an array of integers. Your goal is to move each element into one of two non-empty sets, $A$ and $B$, such that the average of the elements in set $A$ is equal to the average of the elements in set $B$. This is a mathematically intensive problem because the condition "average of $A$ equals average of $B$" is equivalent to saying that the average of set $A$ must also be equal to the average of the entire original array.

Why is this asked in interviews?

This is a "Hard" difficulty problem asked by companies like Microsoft and TikTok. It tests mathematical insight, knowledge of the "Subset Sum" problem, and optimization techniques like bitmasking or early pruning. Interviewers want to see if you can transform a problem about averages into a problem about sums, which is much easier to handle with standard algorithms. It's a deep dive into the Array, Math, Bit Manipulation, Dynamic Programming interview pattern.

Algorithmic pattern used

The problem is a variation of the Subset Sum problem, which is typically solved using Dynamic Programming or Meet-in-the-Middle. The key mathematical insight is: if the total sum is $S$ and total length is $N$, and set $A$ has length $k$ and sum $s_k$, then $s_k / k = S / N$, or $s_k = S \cdot k / N$. Since $s_k$ must be an integer, $S \cdot k$ must be divisible by $N$. This drastically reduces the number of possible sizes $k$ we need to check. We then use DP or bitsets to see if a subset of size $k$ with sum $s_k$ exists.

Example explanation (use your own example)

Suppose you have an array [1, 5, 7, 11]. The total sum is 24 and $N=4$. The average is $24/4 = 6$. We need to find a subset $A$ with average 6. Possible sizes $k$ for $A$ are 1, 2, or 3. If $k=1$, we need a sum of $6 \cdot 1 = 6$. No single element is 6. If $k=2$, we need a sum of $6 \cdot 2 = 12$. Elements (5, 7) sum to 12. Their average is $12/2 = 6$. The remaining elements (1, 11) also sum to 12, and their average is $12/2 = 6$. Since both sets have the same average, the answer is true.

Common mistakes candidates make

• Floating point errors: Trying to compare averages using division and floats instead of using the cross-multiplication or divisibility check.
• Ignoring constraints: Not checking if $S \cdot k / N$ is an integer before searching for the sum.
• TLE (Time Limit Exceeded): Using a basic recursive subset sum without memoization or bitset optimization.
• Empty sets: Forgetting that both sets $A$ and $B$ must be non-empty.

Interview preparation tip

Practice the Subset Sum problem and its variations. This problem is essentially Subset Sum with an added constraint on the number of elements. Learning how to use bitsets to represent possible sums (where the $i$-th bit being set means sum $i$ is possible) is a powerful technique for these types of problems.