LeetCode 0517. Super Washing Machines Solution in Java, C++, Python & More | Explanation + Code

Description

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:

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:

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:

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 <= 104
• 0 <= machines[i] <= 105

Solutions

Solution 1: Greedy

If the total number of clothes in the washing machines cannot be divided evenly by the number of washing machines, it is impossible to make the number of clothes in each washing machine equal, so we directly return -1.

Otherwise, suppose the total number of clothes in the washing machines is s, then the number of clothes in each washing machine will eventually become k = s / n.

We define a_i as the difference between the number of clothes in the i-th washing machine and k, that is, a_i = machines[i] - k. If a_i > 0, it means that the i-th washing machine has extra clothes and needs to pass them to the adjacent washing machine; if a_i < 0, it means that the i-th washing machine lacks clothes and needs to get them from the adjacent washing machine.

We define the sum of the differences in the number of clothes in the first i washing machines as s_i = ∑_{j=0}^{i-1} a_j. If we regard the first i washing machines as one group and the remaining washing machines as another group. Then if s_i is a positive number, it means that the first group of washing machines has extra clothes and needs to pass them to the second group of washing machines; if s_i is a negative number, it means that the first group of washing machines lacks clothes and needs to get them from the second group of washing machines.

Then there are the following two situations:

1. The maximum number of times clothes need to be moved between the two groups is max_{i=0}^{n-1} \lvert s_i \rvert;
2. A washing machine in the group has too many clothes and needs to move clothes to both sides, the maximum number of times clothes need to be moved is max_{i=0}^{n-1} a_i.

We take the maximum of the two.

The time complexity is O(n), where n is the number of washing machines. The space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def findMinMoves(self, machines: List[int]) -> int: n = len(machines) k, mod = divmod(sum(machines), n) if mod: return -1 ans = s = 0 for x in machines: x -= k s += x ans = max(ans, abs(s), x) return ans(code-box)

class Solution { public int findMinMoves(int[] machines) { int n = machines.length; int s = 0; for (int x : machines) { s += x; } if (s % n != 0) { return -1; } int k = s / n; s = 0; int ans = 0; for (int x : machines) { x -= k; s += x; ans = Math.max(ans, Math.max(Math.abs(s), x)); } return ans; } }(code-box)

class Solution { public: int findMinMoves(vector<int>& machines) { int n = machines.size(); int s = accumulate(machines.begin(), machines.end(), 0); if (s % n) { return -1; } int k = s / n; s = 0; int ans = 0; for (int x : machines) { x -= k; s += x; ans = max({ans, abs(s), x}); } return ans; } };(code-box)

func findMinMoves(machines []int) (ans int) { n := len(machines) s := 0 for _, x := range machines { s += x } if s%n != 0 { return -1 } k := s / n s = 0 for _, x := range machines { x -= k s += x ans = max(ans, max(abs(s), x)) } return } func abs(x int) int { if x < 0 { return -x } return x }(code-box)

function findMinMoves(machines: number[]): number { const n = machines.length; let s = machines.reduce((a, b) => a + b); if (s % n !== 0) { return -1; } const k = Math.floor(s / n); s = 0; let ans = 0; for (let x of machines) { x -= k; s += x; ans = Math.max(ans, Math.abs(s), x); } return ans; }(code-box)