Minimum number of coin moves required to make number of coins in each position of a list equal

Question

I came across following question, asked in a interview:

You are given an array coin of size n, where coin[i] denotes the number of coins at position i. A "move" consists of moving some number of coins from position i to either position i+1 or i-1. What is the minimum number of moves necessary to redistribute the coins such that each position has exactly one coin on it? You are guaranteed that there are the same number of coins as there are slots into which to distribute them.

As an example, given the input

 [3, 0, 0, 0, 3, 0, 1]

the output is

[1, 1, 1, 1, 1, 1, 1]

with four moves required:

• Move two coins from pile 0 to pile 1.
• Move one coin from pile 1 to pile 2.
• Move one coin from pile 4 to pile 3.
• Move one coin from pile 4 to pile 5.

What is an efficient way of solving this problem?

Answer 1

You just have to scan the inside borders and count the ones where a transfer is required . This count is the minimum number of moves.

A Python code to find this minimum :

def nb_moves(game):
    N=len(game)-1 # number of inside borders.
    sum = -1
    for i in range(N):
        sum += game[i]
        if i == sum : N -= 1 # no transfer needed between cells i and i+1 . 
    return N

Indeed, Let N be this count . N is clearly a minimum for the number of moves. Moreover, this minimum can be reached:

• Cells can be grouped in zero-sum blocks, with N inside borders in total.

• There are no cells that must be filled by both sides, since the final number of coins in this cell would be > 1.

• If there are cells that must be emptied by both sides, this is done first: the two borders are treated in two moves, cutting the block in two balanced blocks and a cell set to 1.

• The remaining blocks are monotonic, and can be solved from left to right or right to left.

This way each inner border is crossed once and only once.

An implementation is remarkably explained in @templatetypedef's post.

Some tries:

In [275]: solve([3, 0, 0, 0, 3, 0, 1])
Out[275]: 4

In [276]: solve([2,2,0,0])
Out[276]: 3

In [277]: solve([1,2,0,1])
Out[277]: 1