Formatted question description: https://leetcode.ca/all/517.html
517. Super Washing Machines (Hard)
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 representing the number of dresses in each washing machine from left to right on the line, you should find 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.
Example1
Input: [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
Example2
Input: [0,3,0] Output: 2 Explanation: 1st move: 0 < 3 0 => 1 2 0 2nd move: 1 2 > 0 => 1 1 1
Example3
Input: [0,2,0] Output: 1 Explanation: It's impossible to make all the three washing machines have the same number of dresses.
Note:
 The range of n is [1, 10000].
 The range of dresses number in a super washing machine is [0, 1e5].
Companies:
Amazon
Related Topics:
Math, Dynamic Programming
Solution 1. Greedy
Let total
be the total number of dresses in the machines. It’s obvious that the problem is solvable if total
is divisible by N
.
Let avg = total / N
, which is the target number for all the machines.
Let diff[i] = machines[i]  avg
.
Now consider we separate the machines into two parts.
[ left part ]  [ right part ]
The diff
must satisfy the following equation for any 0 <= k < N
so as to reach balance.
sum{ diff[i]  0 <= i < k } = sum{ diff[i]  k <= i < N }
The minimum number of moves must be at least euqal to  sum{ diff[i]  0 <= i < k } 
.
Let sum(k) = sum{ diff[i]  0 <= i < k }
, we know the answer is at least  sum(k) 
for any 0 <= k < N
.
In other words, the answer is at least max{ sum(i)  0 <= i < N }
.
Is there any other situations to consider?
Yes, what if the  diff 
is greater than  sum 
?
For example, assume diff = [3, 5]
, we have sum = [3, 2]
and thus  sum  = [3, 2]
. But max(sum) = 3
is not enough because max(diff) = 5
. We at least need 5 moves to reach balance.
Then we should consider max(diff)
? Not really. We only need to consider max(diff)
.
Why doesn’t diff
matters when it’s negative?
Because it can add 2
in a single move. For example, for input [3, 0, 3]
, diff = [1, 2, 1]
, we can balance the machine in the middle in only one move.
In sum, the minimum number of moves is max( max(sum), max(diff) )
.
Now let’s consider some examples:
input  1  0  5 

diff  1  2  3 
sum  1  3  0 
So max(diff) = 3, max(sum) = 3
, the result is 3
.
input  0  3  0 

diff  1  2  1 
sum  1  1  0 
So max(diff) = 2, max(sum) = 1
, the result is 2
.
input  0  0  3  5 

diff  2  2  1  3 
sum  2  4  3  0 
So max(diff) = 3, max(sum) = 4
, the result is 4
.
// OJ: https://leetcode.com/problems/superwashingmachines/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/superwashingmachines/solution/
class Solution {
public:
int findMinMoves(vector<int>& machines) {
int N = machines.size(), total = accumulate(machines.begin(), machines.end(), 0);
if (total % N) return 1;
int avg = total / N, sum = 0, maxAbsSum = 0, maxDiff = 0;
for (int n : machines) {
int diff = n  avg;
maxDiff = max(maxDiff, diff);
sum += diff;
maxAbsSum = max(maxAbsSum, abs(sum));
}
return max(maxAbsSum, maxDiff);
}
};
Solution 2.
Same as Solution 1, but shorter.
// OJ: https://leetcode.com/problems/superwashingmachines/
// Time: O(N)
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/79938/veryshorteasyjavaonsolution
class Solution {
public:
int findMinMoves(vector<int>& m) {
int sum = accumulate(m.begin(), m.end(), 0), N = m.size();
if (sum % N) return 1;
int target = sum / N, ans = 0, cnt = 0;
for (int i = 0; i < N; ++i) {
cnt += m[i]  target;
ans = max(ans, max(abs(cnt), m[i]  target));
}
return ans;
}
};
Java

class Solution { public int findMinMoves(int[] machines) { int sum = 0; for (int num : machines) sum += num; int length = machines.length; if (sum % length != 0) return 1; int mean = sum / length; int[] differences = new int[length]; for (int i = 0; i < length; i++) differences[i] = machines[i]  mean; int moves = 0; int prefixSum = 0, max = 0; for (int i = 0; i < length; i++) { int difference = differences[i]; prefixSum += difference; max = Math.max(max, Math.abs(prefixSum)); moves = Math.max(moves, Math.max(max, difference)); } return moves; } }

// OJ: https://leetcode.com/problems/superwashingmachines/ // Time: O(N) // Space: O(1) // Ref: https://leetcode.com/problems/superwashingmachines/solution/ class Solution { public: int findMinMoves(vector<int>& machines) { int N = machines.size(), total = accumulate(machines.begin(), machines.end(), 0); if (total % N) return 1; int avg = total / N, sum = 0, maxAbsSum = 0, maxDiff = 0; for (int n : machines) { int diff = n  avg; maxDiff = max(maxDiff, diff); sum += diff; maxAbsSum = max(maxAbsSum, abs(sum)); } return max(maxAbsSum, maxDiff); } };

class Solution(object): def findMinMoves(self, machines): """ :type machines: List[int] :rtype: int """ if sum(machines) % len(machines) != 0: return 1 target = sum(machines) / len(machines) total = 0 ans = 0 for v in machines: total += target  v ans = max(ans, abs(total), v  target) return ans