Given a set of numbers, find the majority group (non equal numbers)

Question

Suppose the given set is $\{0.01,0.2,4,0.3\}$ then the result should be $1,2,4$ respectively, this means finding the largest (at least $n/2 + 1)$ group with the smallest variance. My problem is how to classify such groups so I could calculate the variance?

Answer 1

For a set of $m$ numbers $a_j$, the variance is $$ \frac{1}{m} \sum_j a_j^2 - \frac{1}{m^2}\left(\sum_j a_j\right)^2 $$ If you have $n$ numbers $a_1, \ldots, a_n$, sorted in increasing or decreasing order, and you want a subset of size $m$ with least possible variance, it's easy to see that you'll want to take $\{a_k, \ldots, a_{k+m-1}\}$ for some $k$. So there are not too many cases to try.