World's most popular travel blog for travel bloggers.

# [Solved]: Leveling array values with the smallest move

, ,
Problem Detail:

I'm not an expert of the theory of algorithm, so please forgive me if this problem is nonsense, but I want to find good algorithm to solve below problem.

There is a array of integer each of which has been assigned with random initial value such like [1,5,-3,4] or [123, 543, 295, -703, …]

You move values from one element of the array to another to achieve smaller variance. For [1,5,-3,4], the trivial final state is [2,2,2,1].

There is a constraint. The total amount of moving distance should be as small as possible. There are many paths to move [1,5,-3,4] to [2,2,2,1], but the following way should be worse one:

1. move 1 from the fourth element to the first one.
• [1,5,-3,4] -> [2,5,-3,3] (distance = 1 * 3)
2. move 3 from the second element to the third one.
• [2,5,-3,3] -> [2,2,0,3] (distance = 3 * 1)
3. move 3 from the fourth element to the third one.
• [2,2,0,3] -> [2,2,2,1] (distance = 2 * 1)

(total distance: 8)

because there is shorter (better) way to achieve this:

1. move 3 from the fourth element to the third one.

• [1,5,-3,4] -> [1,5,-1,2] (distance = 2 * 1)
2. move 2 from the second element to the third one.

• [1,5,-1,2] -> [1,3,1,2] (distance = 2 * 1)
3. move 2 from the fourth element to the third one.
• [2,2,0,3] -> [2,2,2,1] (distance = 2 * 1)

(total distance 6)

What is the algorithm which can find the shortest path to level values of array?

#### Answered By : Yuval Filmus

Your problem seems to be the same as that of calculating the Earth mover distance between the starting and target distributions. Wikipedia suggests using the Hungarian algorithm to calculate the distance.