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?