**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:

- The average,
- The mode,
- 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

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