Super Washing Machines

Problem Description

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.

Key Insights

• The total number of dresses must be divisible by the number of machines for it to be possible to equalize the dresses.
• The target number of dresses per machine is calculated as the total dresses divided by the number of machines.
• The maximum number of moves needed to balance dresses can be determined by considering the machines that have excess dresses, as well as those that are deficient.

Space and Time Complexity

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

Solution

To solve the problem, we need to first check if it's possible to equalize the dresses across all machines by checking if the total number of dresses is divisible by the number of machines. If it is not, we return -1.

We then calculate the target number of dresses per machine. For each machine, we track the excess or deficiency of dresses. The maximum moves required can be computed by considering the maximum of:

1. The total excess dresses (how many dresses need to be moved to achieve balance).
2. The maximum deficiency of any machine (how many more dresses that machine needs to reach the target).
3. The number of dresses that need to be moved to adjacent machines.

Code Solutions