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.
We check if balancing is possible. Then, for each machine, we track the running sum of differences and the local difference. The answer is the maximum of these values.
If the total number of dresses is not divisible by the number of machines, it’s impossible. Otherwise, for each machine, compute the running sum of the difference from the target. The answer is the maximum of the absolute value of the running sum and the local difference at each machine.
classSolution {
public:int findMinMoves(vector<int>& machines) {
int n = machines.size(), total =0;
for (int x : machines) total += x;
if (total % n !=0) return-1;
int avg = total / n, res =0, sum =0;
for (int x : machines) {
int diff = x - avg;
sum += diff;
res = max(res, max(abs(sum), diff));
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
publicintfindMinMoves(int[] machines) {
int n = machines.length, total = 0;
for (int x : machines) total += x;
if (total % n != 0) return-1;
int avg = total / n, res = 0, sum = 0;
for (int x : machines) {
int diff = x - avg;
sum += diff;
res = Math.max(res, Math.max(Math.abs(sum), diff));
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
funfindMinMoves(machines: IntArray): Int {
val n = machines.size
val total = machines.sum()
if (total % n !=0) return -1val avg = total / n
var res = 0var sum = 0for (x in machines) {
val diff = x - avg
sum += diff
res = maxOf(res, kotlin.math.abs(sum), diff)
}
return res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution:
deffindMinMoves(self, machines: list[int]) -> int:
n = len(machines)
total = sum(machines)
if total % n !=0:
return-1 avg = total // n
res =0 s =0for x in machines:
diff = x - avg
s += diff
res = max(res, abs(s), diff)
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
pubfnfind_min_moves(machines: Vec<i32>) -> i32 {
let n = machines.len() asi32;
let total: i32= machines.iter().sum();
if total % n !=0 { return-1; }
let avg = total / n;
letmut res =0;
letmut sum =0;
for&x in&machines {
let diff = x - avg;
sum += diff;
res = res.max(sum.abs()).max(diff);
}
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
functionfindMinMoves(machines: number[]):number {
constn=machines.length;
consttotal=machines.reduce((a, b) =>a+b, 0);
if (total%n!==0) return-1;
constavg= Math.floor(total/n);
letres=0, sum=0;
for (constxofmachines) {
constdiff=x-avg;
sum+=diff;
res= Math.max(res, Math.abs(sum), diff);
}
returnres;
}