Making Every Value Equal
Given n integers, choose a single target value and change every number to it. Changing a
number by one costs one move. Print the fewest total moves.
The target must be an integer but may be any integer, not only one from the list.
1 2 3 -> 2 meet at 2
1 100 1 100 -> 198
5 -> 0
## Why a table is the wrong instinct
The shape is familiar from problem 560, which places k mailboxes along a line and genuinely
needs a table, because a partition into k blocks has to be chosen.
Here k is 1. There is no partition, so there is nothing to tabulate, and a table over
candidate targets is not even finite: the target ranges over all integers.
Recognising that the k = 1 case of a partition DP is usually a closed form is worth carrying
away. It is also the base case that problem 560's table calls, so the two fit together.
## The target is the median
Sort the values and take the middle one. Then the answer is the sum of |x - median|.
## Why the median and not the mean
Consider a target t and ask what happens on moving it up by 1. Every value below t gets one
move further, and every value above gets one move closer:
change = (how many are <= t) - (how many are > t)
So the total cost falls while fewer than half the values are at or below t, and rises once
more than half are. The turning point is where the counts balance, which is exactly the median.
The MEAN minimises the sum of SQUARED distances, not absolute ones, and it is the wrong answer
here. On 1 1 1 1 1000000000 the mean is 200000000.8, and rounding it to 200000000
costs 1599999996 moves. The median is 1 and costs 999999999.
The mean is dragged towards the single far value; the median ignores how far away it is and only counts that it is one value out of five. That is the whole difference, and it is why one outlier is enough to separate them.
## When n is even
Both middle values, and every integer between them, give exactly the same total. The argument above says why: between them the counts balance and the cost is flat.
So either middle index works and no tie-break is needed. 1 2 answers 1 whichever of 1 or 2
is chosen.
## Overflow
200000 values spanning 2 * 10^9 reach 4 * 10^14 moves, so use 64 bits. That is still
exact in a double, so JavaScript needs nothing special.
## Cost
Time O(n log n) for the sort. Space O(n).
A linear-time selection would make it O(n), but sorting is simpler and fast enough here.