Super Washing Machines

Problem Statement

In this problem, we are provided with n super washing machines arranged in a line. Each machine initially contains a certain number of dresses, which can also be zero (meaning the machine is empty). During each move, you have the flexibility to select any number of washing machines, between 1 and n, and shift one dress from each selected machine to one of its adjacent machines simultaneously.

The goal is to determine the minimum number of moves required so that all the washing machines have an equal number of dresses. If it's impossible to balance the dresses among the machines, the function should return -1.

The output should be a single integer representing the minimum number of moves required or -1 if equal distribution is unattainable.

Examples

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

Approach and Intuition

• Understanding the Movement:

  • The task allows you to transfer one dress per move from any selected machine to its adjacent one. This simultaneous action requires precise coordination to ensure every machine ends up with the same amount of dresses.

• Key Observations:

  • The total number of dresses across all machines must be divisible by n (the total number of machines) for a uniform distribution to be possible. If not, return -1 immediately.
  • The problem translates into finding out how to efficiently move excess dresses from machines that have more than the average to those that have less.

• Algorithm Design:

  • First, calculate the average number of dresses per machine. This is done by summing all dresses and dividing by the number of machines.
  • Assess the deficit or surplus of dresses per machine relative to this average.
  • As you iterate through the machines, keep a running total of the deficit/surplus. This provides insight into the cumulative shifts needed up to that point.
  • The maximum value of the absolute cumulative shifts at any point in your iteration will indicate the minimum moves required. This is because, at that point, you’ve had the greatest imbalance that had to be corrected through moves.

Example Analyses:

1. For machines [1,0,5], the total is 6. Divided by 3 (number of machines), the average is 2. Directly from the first machine to the second, then to the third, gradually achieving uniform distribution in three moves.
2. For machines [0,3,0], from the middle to both sides to balance in two moves.
3. For machines [0,2,0], trying to balance them as each move leads away from uniformity since the total dresses are not divisible by the number of machines.

Each example underscores the delicate nature of redistribution and the direct dependence on the initial setup of the dresses in the machines.

Solutions

class Solution {
  public int minimumMoves(int[] washers) {
    int totalMachines = washers.length, totalDresses = 0;
    for (int count : washers) totalDresses += count;
    if (totalDresses % totalMachines != 0) return -1;
    
    int targetDresses = totalDresses / totalMachines;
    for (int i = 0; i < totalMachines; i++) washers[i] -= targetDresses;
    
    int runningSum = 0, peakSum = 0, interimMax = 0, finalResult = 0;
    for (int load : washers) {
      runningSum += load;
      peakSum = Math.max(peakSum, Math.abs(runningSum));
      interimMax = Math.max(peakSum, load);
      finalResult = Math.max(finalResult, interimMax);
    }
    return finalResult;
  }
}