One can prove that the minimum number of steps is given when every number sum up to the median of all elements.

If the numbers aren't all equal modulo d, then it's impossible because no matter what you do, their moduli by d are invariant. Otherwise, the number of steps won't change if you have the same sequence, but subtract each element's remainder modulo d from it, so all the elements are divisible by d. And now, just imagine that you divided every element by d; the number of steps for the original sequence with d is the same as for this new sequence with d=1. So the problem simplifies to d=1.

Now to d=1. It's similar to what MDantas said, but more precisely: if the number of elements is odd, then you want to get all the numbers to their median, and if it's even, then there's no single median — there's the (n/2)th and (n/2+1)st number in the sorted order, and the number of steps is the same if you get all the numbers to any value between those two, inclusive.

Now to the proof. If the numbers are equal, you don't need to do anything. Otherwise, imagine you want to get all the numbers a[i] to x, and that there's such an i that a[i] < x <= a[i+1] (it's obvious that if x <= a[1] or x > a[n], then there's a better solution obtained by increasing resp. decreasing x). Then the number of steps is sum(j=1..n): |a[j]-x| = sum(j=i+1..n): (a[j]-x) + sum(j=1..i): (x-a[j]) By decreasing x, i numbers move closer to x and n-i numbers further from it, so the answer increases by n-2i. If the solution is optimal, then this step can't decrease the answer, so n >= 2i. By an analogous process with increasing x with a[i] <= x < a[i+1], we get n <= 2i. That leads to the median for sequences of odd length and the 2 next-to-medians for those of even length.