We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Super Washing Machines

Number: 517

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given n washing machines on a line where each machine holds some number of dresses, determine the minimum number of moves required to redistribute the dresses so that every machine has the same number. In one move, you can choose any set of machines and move one dress from each chosen machine to an adjacent machine. If it is impossible to achieve equal dresses across all machines, return -1.

Key Insights

  • The total number of dresses must be divisible by the number of machines; otherwise, it's impossible.
  • The target number of dresses per machine is the average (total dresses / n).
  • At each machine, calculate the difference (current - target). This difference tells if the machine needs to give away dresses (if positive) or receive dresses (if negative).
  • Use a running total (cumulative balance) to keep track of the net dresses that should move across machines. The maximum absolute cumulative balance indicates the moves caused by “passing” dresses along the line.
  • The maximum number of moves required at any machine is the maximum of:
    1. The absolute value of the cumulative sum (tracking dresses passing by).
    2. The number of dresses that need to be dumped from one machine (if current count exceeds target).

Space and Time Complexity

Time Complexity: O(n) – We pass over the array of machines once. Space Complexity: O(1) – Only a constant amount of extra space is used.

Solution

The solution works by first ensuring that the total number of dresses can be evenly distributed across all machines. Next, for each machine, we calculate the difference between its current number of dresses and the target number. As we iterate through the machines, we maintain a running total (cumulative balance) of these differences. The key insight is that at any machine, the number of moves required will be the maximum of the absolute cumulative balance (which represents dresses being transferred across machines) and the local surplus (if any). The answer is the maximum of these values over all machines.

Code Solutions

# Calculate the minimum number of moves to balance the dresses in washing machines.
def findMinMoves(machines):
    total_dresses = sum(machines)
    n = len(machines)
    
    # Check if it is possible to distribute dresses evenly.
    if total_dresses % n != 0:
        return -1
    
    average = total_dresses // n
    max_moves = 0
    cumulative_balance = 0
    
    # Iterate through each machine to determine the moves needed.
    for index, dresses in enumerate(machines):
        # Difference between the current number and target.
        diff = dresses - average
        cumulative_balance += diff  # Running sum of differences.
        # The required moves is the maximum of the local surplus and the absolute cumulative balance.
        max_moves = max(max_moves, abs(cumulative_balance), diff)
    
    return max_moves

# Example usage:
machines1 = [1, 0, 5]  # Output should be 3
machines2 = [0, 3, 0]  # Output should be 2
machines3 = [0, 2, 0]  # Output should be -1

print(findMinMoves(machines1))
print(findMinMoves(machines2))
print(findMinMoves(machines3))
← Back to All Questions