Suppose there are n super washing machines arranged in a row. Initially, each machine may contain some clothes or be empty.

In each step, you may choose any m (1 <= m <= n) washing machines. At the same time, each selected machine sends one piece of clothing to an adjacent machine.

Given an integer array machines representing the number of clothes in each washing machine from left to right, return the minimum number of steps needed to make the number of clothes remaining in every machine equal. If it is impossible, return -1.

Example 1:

Input:machines = [1,0,5]
Output:3
Explanation:
First step:    1     0 <-- 5    =>    1     1     4
Second step:    1 <-- 1 <-- 4    =>    2     1     3
Third step:    2     1 <-- 3    =>    2     2     2

Example 2:

Input:machines = [0,3,0]
Output:2
Explanation:
First step:    0 <-- 3     0    =>    1     2     0
Second step:    1     2 --> 0    =>    1     1     1

Example 3:

Input:machines = [0,2,0]
Output:-1
Explanation:
It is impossible to make all three washing machines contain the same number of clothes.

Constraints:

• n == machines.length
• 1 <= n <= 104
• 0 <= machines[i] <= 105

Approach

#

The main idea is to traverse the array.

First, make one pass to determine whether a solution is possible and to calculate the average number of clothes, avg, for each position.

The next step follows from an important observation. If a position contains K pieces of clothing and K>avg, the final answer must be at least K-avg. Regardless of what happens at the other machines, this machine must spend K-avg steps sending away its excess clothes.

We can also maintain a value cur while traversing the array. Imagine an invisible hand changing the number of clothes in every machine to avg as it moves across the array. Excess clothes are treated as surplus, while missing clothes are treated as a deficit. This has the benefit of assigning each transfer to the relevant boundary. The following example makes this easier to understand.

示例：          [5, 0, 7], avg = 12 / 3 = 4
在遍历时的`cur`值：[1, -3, 0]

For this array, the maximum absolute value of cur is the total time required. If we look only at position 1, the middle position, we see that it needs four fills to reach avg. One fill comes from the left and three come from the right, but these two periods can overlap. The value of cur represents deficits and surpluses well. When the deficit at a position is k, it means that even after balancing the machines to its left internally, they are still short of k items, which must be moved over from the right of cur; this k is the minimum transfer time. When the surplus is k, it similarly means that the machines at and to the left of cur have k extra items after internal balancing. They must be transferred to the right of cur, and the transfer must pass through cur, so these k moves cannot overlap and require at least k steps.

Thus, cur controls the global number of transfers. There is still one limitation. Consider the following example:

示例：          [0, 3, 0], avg = 3 / 3 = 1
在遍历时的`cur`值：[-1, 1, 0]

In this example, cur misses a crucial point: the machine containing 3 pieces must spend two steps to transfer all its excess clothes. But cur does not know that the values -1 and 1 it encounters cannot overlap; both come from the machine containing 3. We therefore need to consider the effects of both cur and K-avg on the final result.

Rust Code

#

# struct Solution;
impl Solution {
    pub fn find_min_moves(machines: Vec<i32>) -> i32 {
        let sum: i32 = machines.iter().sum();
        let n = machines.len() as i32;
        if sum % n != 0 {
            return -1;
        }
        let avg = sum / n;
        let mut res = 0;
        let mut cur = 0;
        for mut m in machines {
            m -= avg;
            cur += m;
            res = res.max(cur.abs()).max(m);
        }
        res
    }
}

C++ Code

#

class Solution {
public:
    int findMinMoves(vector<int>& m) {
        int n = m.size();
        int sum = 0;
        for (auto & t : m) sum += t;
        if (sum % n != 0) return -1;
        int per = sum / n;
        sum = 0;
        int res = 0;
        for (auto & t : m) {
            t -= per;
            sum += t;
            res = max(res, abs(sum));
            res = max(res, t);
        }
        return res;
    }
};