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

Answer 2

There's a nice observation we can use to solve this problem in O(n) time. The trick is to look at the leftmost element of the array. There are three cases of what can happen if you do:

• The leftmost value is 1. In this case, we're never going to want to move this coin, and no coins need to be moved here. We can therefore imagine cutting this element off of the array and solving the remaining subproblem. For example, the array [1, 0, 0, 3] would be converted to the array [0, 0, 3].

• The leftmost value is greater than 1. In this case, we know that we will have to move all but one coin off of this position by shifting them to the right. We can therefore make that move, leaving a 1 on the far left side, and then disregard that element via the logic in the above case. For example, [3, 2, 0, 0, 0] would become [1, 4, 0, 0, 0], and then we'd drop the 1 to get [4, 0, 0, 0].

• The leftmost value is 0. In this case, we will need to make some series of moves to cover this slot. The question then is which moves we make to do this. The observation we need to make here is that the most efficient way to cover this slot is to find the first slot k where the sum of the number of coins at or before position k is at least k, then to pick enough coins out of that pile to reach the leftmost position and make k - 1 moves sending those coins over. To see why this is, first note that there's no optimal strategy that would involve sending any coins from the right of position k through position k to fill the gap in the leftmost slot, since if we did this we'd have too many coins in the first k slots to go around and would have to send some back. So that means that we know any optimal solution must consist of using coins from the first k slots to fill in the gap. Now, imagine that there's a better solution than moving coins from pile k to the left. That would mean that we're trying to cover the first k - 1 slots using fewer than k - 1 coins, leaving a hole that can then only be filled by moving pile k to the left. In other words, any solution is going to involve moving pile k leftward, so moving k leftward first will never be suboptimal.

Here's an implementation of the above idea that runs in time O(n):

int moves = 0;
for (int i = 0; i < n; i++) {
    /* Case 1 requires no action. */

    /* Case 2: leftmost pile has more than one coin. */
    if (coins[i] > 1) {
        coins[i + 1] += coins[i] - 1;
        /* No need to edit coins[i]; we won't touch it again. */
    }

    /* Case 3: Find a pile and shift it back. */
    else if (coins[i] == 0) {
        /* Total up coins until a free spot is found. */
        int k = 1;
        int zeroes = 1;
        int cumTotal = coins[i + k];

        while (cumTotal <= k) {
            k++;
            if (coins[k] == 0) zeroes++;
            cumTotal += coins[i + k];
        }

        /* Remove from that pile enough coins to cover all the zeroes encountered. */
        coins[k] -= zeroes;
        moves += k;

        /* Continue our scan after this position. */
        i = k;
    }
}
return moves;

Answer 3

Considering only one coin can be moved at a time:
A simple solution to this problem is to iterate over all positions and from each position which have 0 coin, iterate from left to right to find a position with more than one coin and keep track total move require to bring coin from that position to the initial position.

int minimumCoinMoves(vector<int>&coins) {
    int n = coins.size();
    int moves = 0;
    for (int i = 0; i < n; ++i) {
        if (coins[i] == 0) {
            for (int j = 0; j < n; ++j) {
                if (coins[j] > 1) { // fill up ith place with coin in jth place
                    coins[i] = 1;
                    coins[j]--;
                    moves += abs(j - i); // total moves from jth to ith place
                    break;
                }
            }
        }
    }
    return moves;
}

If we assume we have n coins, then this approach will cost us time complexity of O(n * n). This complexity may not be feasible in case where the value of n is very large. We may reduce our complexity to O(n) by simply modifying above solution to keep track of positions with extra coins in other vector and retrieving coins moving from those place in all positions with 0 coins from left to right.

int minimumCoinMoves(vector<int>&coins) {
    int n = coins.size();
    int moves = 0;
    vector<int>extraCoinIndices;
    for (int i = 0; i < n; ++i) {
        if (coins[i] > 1) {
            extraCoinIndices.push_back(i);
        }
    }
    int ptr = 0;
    for (int i = 0; i < n; ++i) {
        if (coins[i] == 0) {
            moves += abs(extraCoinIndices[ptr] - i);
            coins[i] = 1;
            coins[ extraCoinIndices[ptr] ]--;
            if (coins[ extraCoinIndices[ptr] ] == 1) ptr++;
        }
    }
    return moves;
}

EDIT:
Considering any number of coins can be moved at a time:
If we consider that any number of coins can be moved from a position in a move, we may do following changes to solve it in O(n).

int minimumCoinWithAnyNumberMoves(vector<int>&coins) {
    int n = coins.size();
    int moves = 0;
    int farZero = -1;
    int extraCoins = 0;
    for (int i = 0; i < n; ++i) {
        if (coins[i] == 0) {
            if (extraCoins > 0) {
                extraCoins--;
                moves++;
                continue;
            }
            farZero = (farZero == -1) ? i : farZero;
        } else {
            if (farZero == -1) {
                if (extraCoins > 0) moves++;
                extraCoins += (coins[i] - 1);
                continue;
            }
            assert(extraCoins == 0);
            int totZeros = i - farZero;
            moves += totZeros;
            if (coins[i] <= totZeros) {
                farZero = farZero + coins[i];
            } else {
                farZero = -1;
                extraCoins += (coins[i] - totZeros - 1);
            }
        }
    }
    return moves;
}