Super Washing Machines

hard array greedy

Problem

n washing machines on a line; in one move you can transfer 1 dress from any machine to one of its neighbours. Make all equal. Return min moves, or −1.

Inputmachines = [1,0,5]

Output3

If total % n != 0, return −1. Else scan left→right tracking deficit; answer is max bottleneck.

machines

def find_min_moves(machines):
    n = len(machines); total = sum(machines)
    if total % n != 0: return -1
    avg = total // n
    bal = 0; ans = 0
    for x in machines:
        diff = x - avg
        bal += diff
        ans = max(ans, abs(bal), diff)
    return ans

function findMinMoves(machines) {
  const n = machines.length, total = machines.reduce((a, b) => a + b, 0);
  if (total % n !== 0) return -1;
  const avg = total / n;
  let bal = 0, ans = 0;
  for (const x of machines) {
    const diff = x - avg;
    bal += diff;
    ans = Math.max(ans, Math.abs(bal), diff);
  }
  return ans;
}

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

int findMinMoves(vector& machines) {
    int n = machines.size(), total = 0;
    for (int x : machines) total += x;
    if (total % n != 0) return -1;
    int avg = total / n, bal = 0, ans = 0;
    for (int x : machines) {
        int diff = x - avg;
        bal += diff;
        ans = max(ans, max(abs(bal), diff));
    }
    return ans;
}

Explanation

We have machines in a line and each move shifts one dress to a neighbour. We want the fewest moves to equalize them. The neat insight is that the answer is the worst bottleneck we encounter, not a simulation of moves.

First a quick check: if the total number of dresses isn't divisible by n, equalization is impossible and we return -1. Otherwise the target per machine is avg = total / n.

We scan left to right keeping a running balance bal of how many dresses must cross the boundary between the part we've seen and the rest. For each machine, diff = x - avg and bal += diff. The answer is the maximum of |bal| (dresses forced across one gap) and diff (a single overloaded machine can only push out one dress per move).

Example: machines = [1, 0, 5], total 6, avg = 2. Diffs are -1, -2, +3; running balances are -1, -3, 0. The bottleneck is max(|bal|, diff) reaching 3 (the last machine must send out 3 dresses), so the answer is 3.

Because every dress crossing a boundary costs at least one move, and one machine can only output one dress per move, this maximum is exactly the minimum number of moves.

Time: O(n) Space: O(1)