How do you split an array into 2 parts so that the two parts have an equal average?

Question

How do you split an array into 2 parts so that the two parts have an average value? Each section may contain elements that are not adjacent in the array. The only algorithm I can think of is exponential, can we do better?

Answer 1

You can reduce this problem to a sum-subset problem - also here. Here is an idea.

Let A be an array. Calculate S = A[0] + ... + A[N-1] , where N is the length of A For k from 1 to N-1 , let T_k = S * k / N If T_k is an integer, then find a subset A size k that sums with T_k . If you can do this, then everything is ready. If you cannot do this for any k , then such a separation does not exist.

---

Here is the math behind this approach. Suppose that there is a partition on A such that the two parts have the same average value, says X size X and Y size Y are sections where x+y = N Then you must have

 sum(X)/x = sum(Y)/y = (sum(A)-sum(X)) / (Nx) 

therefore a bit of algebra gives

 sum(X) = sum(A) * x / N 

Since the array contains integers, the left side is an integer, so the right side should also be. This motivates the restriction that T_k = S * k / N must be an integer. The only remaining part is to implement T_k as the sum of a subset of size k .