I've not seen this kind of question online or anywhere else, I'm needing a similar algorithm in my opensource application but I'm unable to come up with a good approach (apart from brute force). Any directions would be helpful. :)

You're given an array A of N non-zero integers (A = [a1, a2, a3 ... an]). You're also given a number K, which denotes the number of partitions you need to make. Now you need to output an array with K values such that the array contains the average of N/K which are closest to each other. Also the array A can contain repetitions and is not sorted. One more thing we know is N>>K ( N is very large when compared with K ). It is guaranteed that N is divisible by K.

Other way of thinking (I think): Imagine that we have a 1d universe and there are N points with equal weights and due to gravity we each start merging with each and we need to get the positions of mass when we have only K different mass remaining.

for eg.

A = [1, 2, 3, 8, 9, 10]
K = 2
output = [2, 9]
explaination: see 2 is the average of 1, 2, 3 which are the 3 (N/K = 6/2) numbers closest to each other
              and 9 is the average of 8, 9, 10 which are another 3 (N/K = 6/2) numbers closest to each other