Question

Given an array with non negative numbers, divide the array into two parts such that the average of both the parts is equal. Return both parts (if exist).

Answer 1

Partition an array of non-negative integers into two subsets such that average of both the subsets is equal

Given an array of size N. The task is to partition the given array into two subsets such that the average of all the elements in both subsets is equal. If no such partition exists print -1. Otherwise, print the partitions. If multiple solutions exist, print the solution where the length of the first subset is minimum. If there is still a tie then print the partitions where the first subset is lexicographically smallest.

Examples:

Input : vec[] = {1, 7, 15, 29, 11, 9}

Output : [9, 15] [1, 7, 11, 29]

Explanation : Average of the both the subsets is 12

Input : vec[] = {1, 2, 3, 4, 5, 6}

Output : [1, 6] [2, 3, 4, 5].

Explanation : Another possible solution is [3, 4] [1, 2, 5, 6],

but print the solution whose first subset is lexicographically

smallest.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Observation :

If we directly compute the average of a certain subset and compare it with another subset’s average, due to precision issues with compilers, unexpected results will occur. For example, 5/3 = 1.66666.. and 166/100 = 1.66. Some compilers might treat them as same, whereas some others won’t.

Let the sum of two subsets under consideration be sub1 and sub2, and let their sizes be s1 and s2. If their averages are equal, sub1/s1 = sub2/s2 . Which means sub1*s2 the = sub2*s1.

Also total sum of the above two subsets = sub1+sub2, and s2= total size – s1.

On simplifying the above, we get