# Algorithm to match numbers with minimum number of moves

This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far.

Given a series of numbers, e.g.

[3, 1, 1, 1]


How would one most efficiently turn all of the numbers into the same number, with the minimum number of "moves"? By "move" is meant adding or removing one from a number.

In the above example, the most efficient moves would be:

[1, 1, 1, 1]


This would require 2 moves, reducing the first number twice.

I can't figure out the best way to find this out, given much larger arrays of hundreds of numbers.

I originally tried computing the rounded average number (sum of all divided by length), and then reducing them to the computed average, but the above example broke this, requiring 4 moves instead of 2.

I suppose I could figure:

1. The average,
2. The mode,
3. The median

and get the edit distance of each of them, choosing the minimum distance. However, I am not sure that this would be correct in every single instance. How can I know?

• If domain is limited you can try all possibilities from min to max. Otherwise you may try to use mode or median. May 6, 2014 at 21:45
• Thanks @Bartek. Seems like trying all possibilities would be tremendously inefficient if dealing with hundreds or thousands of numbers. I'll check out mode/median. But are these certain to produce results in every instance? That's my main question. I am looking for a certain, efficient algorithm. May 6, 2014 at 21:48
• Does the number have to be in the set of numbers, or can it be any integer? May 6, 2014 at 22:05
• @TCSGrad It can be any integer, but obviously you would want to pick one that is in between the min and max number. In this case, either 1, 2, or 3. May 6, 2014 at 22:29

The answer is to take the median. One of the properties of the median is that it minimizes the L1 distance to each element. (To make sense of the Wikipedia article, take the probability distribution to be the uniform distribution over your original series of numbers).

This is the algorithm which solves the problem (originally written by dc2):

function median(arr) {
arr.sort(function(a, b) { return a - b; });
var half = floor(arr.length/2);
if ( arr.length % 2 ) {
return arr[half];
} else {
return (arr[half-1] + arr[half]) / 2.0;
}
}

function minl1(arr) {
var moves = 0;
var mdn = median(arr);
for ( var i = 0; i < arr.length; ++i ) {
moves += Math.abs(mdn - arr[i]);
}
return moves;
}

minl1([3, 1, 1, 1]); // -> 2

• Yeah, that did it. Funny how that works. Doesn't seem like the median would do it, but hey. Thanks a lot. May 7, 2014 at 3:15
• See my answer for a proof. May 7, 2014 at 3:54
• @dc2: You can't "make sure" by "trying it out". May 7, 2014 at 7:48
• Just to note: you can calculate median O(n) time May 7, 2014 at 7:53
• @Raphael Is it okay to include OP's code in some other answer, with no reference to OP? May 7, 2014 at 8:33

As TCSGrad mentions, given a list of integers $x_1,\ldots,x_n$, you're looking for the integer $m$ minimizing $$\delta(m) = \sum_{i=1}^n |m - x_i|.$$ It is instructive to compute $\delta(m+1) - \delta(m)$: $$\delta(m+1) - \delta(m) = \sum_{i=1}^n \begin{cases} +1 & m \geq x_i \\ -1 & m < x_i \end{cases} = \#\{i : m \geq x_i\} - \#\{i : m < x_i\}.$$ As $m$ goes from $-\infty$ to $+\infty$, the quantity $\delta(m+1) - \delta(m)$ goes from $-n$ to $n$. Moreover, it switches values only at the points $x_1,\ldots,x_n$. It is not hard to check that an optimal value of $m$ is the minimal point at which $\delta(m+1) - \delta(m) \geq 0$. This minimal point is one of the $x_i$, so the editing distance is $\min(\delta(x_1),\ldots,\delta(x_n))$.

Suppose further that all $x_i$ are distinct and that $n$ is odd. Let $m$ be the median of the $x_i$. Then $\delta(m+1) - \delta(m) = 1$ while $\delta(m) - \delta(m-1) = -1$, and so $m$ is the unique optimum. If $n$ is even then a similar calculation shows that we can choose any point in the interval connecting the medians. Similar but more elaborate reasoning shows that any median is optimal even when the $x_i$ are not distinct. So there is actually no need to calculate $\delta$ on all $x_i$.

• You might have missed it, but this answer (almost) proves that the median is the optimal choice. May 7, 2014 at 4:14
• your answer was excellent and I upvoted it. Unfortunately for me, a little too excellent as I am not that well versed in scientific notation, leaving most of it as rendered garble. That's my problem, not yours. May 7, 2014 at 5:17

The problem can be formulated as a LP problem:

Given a set of $n$ numbers $[a_1,a_2... a_n]$, solve the following LP:

$$\min \sum |a_i - x|$$

(Removed constraints on $x$, which weren't necessary as Raphael pointed out)

Once the LP is solved, you'll get a value of $x$ corresponding to the solution. If $x$ is an integer, you are done - else, round it to the nearest integer.

EDIT: As pointed out in the comments, the objective function should be sum over absolute differences. In order to transform it back to a standard LP, we can rewrite the LP as:

$$\min \sum a'_i$$

subject to:

$$a'_i \geq a_i - x\ \forall i$$ $$a'_i \leq a_i - x\ \forall i$$ $$a'_i, x' \geq 0\ \forall i$$

At the optimal solution, $a_i' = | a_i - x|\ \forall i$, and we can get the value of $x$ from the solution.

• So if I understand this correctly, in my example, x would be 1 - 3, and so I would find the edit distance of 1, 2 and 3, and then do a min on that? May 6, 2014 at 22:45
• @dc2: This would minimize the sum of the distances between each number and $x$, where $x$ is the convergent number. The constraints ensure the LP terminates quickly, and does not search over all integers! May 6, 2014 at 22:46
• Why are the constraints necessary? May 6, 2014 at 23:02