Algorithm to match numbers with minimum number of moves

ignougroup
Problem Detail: 
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?

Asked By : dthree

Answered By : mhum

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
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24469

Leave a Reply