Super Washing Machines Problem
Description
LeetCode Problem 517.
You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.
For each move, you could choose any m (1 <= m <= n) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time.
Given an integer array machines representing the number of dresses in each washing machine from left to right on the line, return the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.
Example 1:
1
2
3
4
5
6
Input: machines = [1,0,5]
Output: 3
Explanation:
1st move: 1 0 <-- 5 => 1 1 4
2nd move: 1 <-- 1 <-- 4 => 2 1 3
3rd move: 2 1 <-- 3 => 2 2 2
Example 2:
1
2
3
4
5
Input: machines = [0,3,0]
Output: 2
Explanation:
1st move: 0 <-- 3 0 => 1 2 0
2nd move: 1 2 --> 0 => 1 1 1
Example 3:
1
2
3
4
Input: machines = [0,2,0]
Output: -1
Explanation:
It's impossible to make all three washing machines have the same number of dresses.
Constraints:
- n == machines.length
- 1 <= n <= 10^4
- 0 <= machines[i] <= 10^5
Sample C++ Code
We first check if the sum of dresses in all machines can be divided by the count of machines. If not, there is no solution. Otherwise, we can always pass one dress from one machine to another and finally all machines have the same number of dresses.
To count the minimum number of moves, since we can operate several machines at the same time, the minium number of moves is the maximum number of necessary operations on every machine.
For a single machine, the number of necessary operations is to pass dresses from one side to another until sum of both sides and itself reaches the average number. We can calculate (required dresses) - (contained dresses) of each side as L and R:
- L > 0 && R > 0: both sides lacks dresses, and we can only export one dress from current machines at a time, so result is abs(L) + abs(R)
- L < 0 && R < 0: both sides contains too many dresses, and we can import dresses from both sides at the same time, so result is max(abs(L), abs(R))
- L < 0 && R > 0 or L >0 && R < 0: the side with a larger absolute value will import/export its extra dresses from/to current machine or other side, so result is max(abs(L), abs(R))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int findMinMoves(vector<int>& machines) {
int len = machines.size();
vector<int> sum(len + 1, 0);
for (int i = 0; i < len; ++i)
sum[i + 1] = sum[i] + machines[i];
if (sum[len] % len) return -1;
int avg = sum[len] / len;
int res = 0;
for (int i = 0; i < len; ++i) {
int l = i * avg - sum[i];
int r = (len - i - 1) * avg - (sum[len] - sum[i] - machines[i]);
if (l > 0 && r > 0)
res = std::max(res, std::abs(l) + std::abs(r));
else
res = std::max(res, std::max(std::abs(l), std::abs(r)));
}
return res;
}
};