Super Washing Machines

Updated on 04 July, 2025
Super Washing Machines header image

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

  • Java
java
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;
  }
}

The provided Java code presents a solution for the problem where you need to balance washers to contain an equal number of dresses with the minimum number of moves.

  • First, it calculates the total number of dresses across all washing machines.
  • It checks if the total number of dresses is evenly divisible by the number of machines. If not, it immediately returns -1 as it's impossible to balance them.
  • It then calculates the target number of dresses per machine (total dresses divided by total machines) and adjusts each washer's count by subtracting this target number to find out the current imbalance.
  • The main part of the code uses variables to track the ongoing sum of imbalances (runningSum), the peak absolute value of this running sum (peakSum), and the highest value among the peakSum and individual washers' imbalances (interimMax). It iterates through the washers, updating these values to account for necessary moves to balance earlier imbalances.
  • The maximum value among all peaks (finalResult) determines the minimum number of moves required to balance all washers.

In essence, this solution provides a method to efficiently determine the minimal adjustments needed by calculating how the imbalances "cascade" throughout the series of washers, updating at each step the worst-case scenario of dresses that must be moved. The algorithm focuses on sequential accumulation of imbalances, optimizing for the worst case to ensure all washers reach equilibrium.

Comments

No comments yet.