# C++ 12 ms O(n) 8 lines

• First. we determine the target dresses we should have in each machine (total dresses / # of machines), and return -1 if it's not an integer.

We then go from left to right, tracking the running balance of dresses we need to move through each machine. If, for example, we have 5 extra dresses so far, and this machine has 2 extra dresses, we need to pass total 7 dresses through that machine (requires 7 steps). Also, we need to track the number of dresses we need to offload from a particular machine (machine[i] - target dresses). This number may be higher than the running balance if dresses are passed both ways, as shown in the example 2.

Example 1: [1, 1, 6, 6, 1], total dresses: 15, target dresses: 3, maximum offload is 3 (6 - 3).
Running balance:[-2][-4][ -1][ 2][ 0]

Example 2: [1, 1, 4, 8, 1], total dresses: 15, target dresses: 3, maximum offload is 5 (8 - 3).
Running balance:[-2][-4][ -3][ 2][ 0]

``````int findMinMoves(vector<int>& machines) {
int totalDresses = 0, size = machines.size();
for (auto i = 0; i < size; ++i) totalDresses += machines[i];
if (totalDresses % size != 0) return -1;

auto targetDresses = totalDresses / size, totalMoves = 0, ballance = 0;
for (auto i = 0; i < size; ++i) {
ballance += machines[i] - targetDresses;
totalMoves = max(totalMoves, max(machines[i] - targetDresses, abs(ballance)));
}
}
``````

• Nice - definitely a bit simpler than my solution. I had a bit of trouble understanding the correctness of your max line so I separated out the cases a little bit. Hope this makes things clearer for others.

``````
int findMinMoves(vector<int>& M) {
int n = M.size();
if (n == 0) return 0;

int s = 0;
for (int d : M) s += d;

if (s % n != 0) return -1;

int target = s / n;
int moves = 0;
int balance = 0;

for (int i = 0; i < n; i++) {
// How much to send left from this machine?
int left = 0;
if (balance < 0) {
left = -balance;
moves = max(moves, left);
}

balance += (M[i] - target);

// If balance is positive, how much to send right?
int right = 0;
if (balance > 0) {
right = balance;
// We cannot send left and right at the same time so we have to
// send left/right separately.
moves = max(moves, left + right);
}
}

return moves;
}
};
``````

• @amaximov Correct, when balance changes from negative to positive, we need to sum dresses we send left and right. In this case, I figured, (left + right) equals (M[i] - target) - we need to send all extra dresses from this machine left and/or right.

I was shooting for a concise code, so I did max(balance, M[i] - target). I agree It could make code harder to read, but folks here seem to like cryptic one-liners in Python, so I thought - what the heck.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.