600. 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.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`