517 Super Washing Machines

17 Super Washing Machines

You havensuper washing machines on a line. Initially, each washing machine has some dresses or is empty.

For eachmove, you could chooseany m(1 ≤ m ≤ n) washing machines, and passone dressof each washing machine to one of its adjacent washing machinesat the same time.

Given an integer array representing the number of dresses in each washing machine from left to right on the line, you should find theminimum number of movesto make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.

Example1

Input:
 [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

Example2

Input:
 [0,3,0]


Output:
 2


Explanation:

1st move:    0 
<
-- 3     0    =
>
    1     2     0    
2nd move:    1     2 --
>
 0    =
>
    1     1     1

Example3

Input:
 [0,2,0]


Output:
 -1


Explanation:

It's impossible to make all the three washing machines have the same number of dresses.

Note:

  1. The range of n is [1, 10000].

  2. The range of dresses number in a super washing machine is [0, 1e5].

The Idea: (not currently working)

  • First check if it is possible to have an equivalent array. This is so, if the all the elements in the array can be equally divisible by the size of the array.

  • The sort the array, and exchange elements from the min and max until the numbers are equivalent. A quicker operation would be to take the difference between them, and accumulate this as the number of exchanges.

def findMindMoves(machines):
    """
    :type machines List[int]
    :rtype: int
    """

    total_sum = sum(machines)
    start = 0
    end = len(machines)

    if (not (((total_sum/end))).is_integer()):
        return -1

    machines.sort()
    swap_count = 0
    while (end > start):

        edge_diff = machines[end - 1] - machines[start]
        if (((edge_diff / 2)).is_integer()):
            swap_count += split_diff
        else:
            swap_count += int(split_diff) - 1

        start+=1
        end-=1

    return int(swap_count)


print(findMindMoves([1,0,5]))
print(findMindMoves([0,3,0]))
print(findMindMoves([0,2,0]))

Last updated