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 representing the number of dresses in each washing machine from left to right on the line, you should find 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.

Example1

Input: [1,0,5]

Output: 3

Explanation: 
1st move:    1     0     1     1     4
2nd move:    1     2     1     3    
3rd move:    2     1     2     2     2   


Example2

Input: [0,3,0]

Output: 2

Explanation: 
1st move:    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:

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

Difficulty: interview

Starter code:

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        

Solutions:
class Solution:
     def findMinMoves(self, machines):
         """
         :type machines: List[int]
         :rtype: int
         """
         if sum(machines) % len(machines) != 0:
             return -1
         mean = sum(machines) // len(machines)
         cum, step = 0, 0
         for x in machines:
             cum += x - mean
             step = max(step, abs(cum), x-mean)
         return step

class Solution:
     def findMinMoves(self, machines):
         """
         :type machines: List[int]
         :rtype: int
         """
         total = sum(machines)
         length = len(machines)
         if total%length!=0:
             return -1
         
         avg = int(total/length)
         cum = 0
         target = 0
         result = 0
         for m in machines:
             cum+=m
             target+=avg
             max_share = m-avg # example [0,3,0] 3 must output 1 to one side at a time, so it needs 2 steps: one for each side.
             result = max(result, abs(target-cum), max_share)
             # When cum-target<0, it means right side must transfer abs(cum-target) to the left side
             # example: [0, 0, 11, 5], avg=4, at the second 0, cum=0, target=2*avg=8, we need to transfer 8-0=8 to the left side
             # the second 0 is the only interface to the right side, so the right side need 8 steps to fill the left side
             
             # When cum-target>0, it means left side must transfer abs(cum-target) to the right side
             # example: [4,3,2,1,0], avg=2, at 3, cum=7, target=2*avg=4, we need to transfer 7-4=3 to the right side
             # 3 is the only interface to the right side, so the left side need 3 steps to fill the right side
         return result;


class Solution:
     def findMinMoves(self, machines):
         """
         :type machines: List[int]
         :rtype: int
         """        
         N = len(machines)
         if sum(machines)%N!=0: return -1
         avg = sum(machines)//N
         
         result = 0
         toNext = 0
         for i in range(N):
             fromPrev = toNext
             toNext = fromPrev+machines[i]-avg
             if fromPrev<0 and toNext>0:
                 result = max(result,-fromPrev+toNext)
             else:
                 result = max(result,abs(fromPrev),abs(toNext))
                         
         return result
             


class Solution:
     def findMinMoves(self, machines):
         """
         :type machines: List[int]
         :rtype: int
         """
         n = len(machines)
         if sum(machines) % n != 0:
             return -1
         
         s = sum(machines)
         k = s//n
         
         presum = 0
         right = 0
         max_net = 0
         for i in range(n):
             presum += machines[i]
             left = -right
             right = presum - k*(i+1)
             net = left + right
             
             max_net = max(max_net, abs(left), abs(right), net)
             
         return max_net
             
             
         


class Solution:
     def findMinMoves(self, machines):
         """
         :type machines: List[int]
         :rtype: int
         """
         sum_before = [0]
         i = 0
         for m in machines:
             sum_before.append(m + sum_before[i])
             i+=1
             
         if sum_before[len(machines)]%len(machines)!=0:
             return -1
         
         average = int(sum_before[len(machines)]/len(machines))
         
         result = 0
         
         i = 0
         for m in machines:
             left_require = average * i - sum_before[i] 
             right_require = average * (len(machines)-i-1) - (sum_before[len(machines)] - sum_before[i+1])
             if left_require > 0 and right_require > 0:
                 max_tran = left_require + right_require
             else:
                 max_tran = max(abs(left_require), abs(right_require))
             result = max(result, max_tran)
             i+=1
                 
         return result

class Solution:
     def findMinMoves(self, machines):
         """
         :type machines: List[int]
         :rtype: int
         """
         total = sum(machines)
         length = len(machines)
         if total%length!=0:
             return -1
         
         avg = int(total/length)
         cnt = 0
         result = 0
         for m in machines:
             cnt += m-avg; #load-avg is "gain/lose"
             result = max(result, abs(cnt), m-avg)
         return result;


class Solution:
   def findMinMoves(self,machines):
     s = sum(machines)
     l = len(machines)
     if s%l: return -1
     a, c, ans = int(s/l), 0, 0
     for x in machines:
       y = x - a
       c += y
       ans = max(ans, y, abs(c))
     return ans
     """
     :type machines: List[int]
     :rtype: int
     """

class Solution:
     def __init__(self):
         pass
         
     def findMinMoves(self, machines):
         """
         :type machines: List[int]
         :rtype: int
         """
         
         N = len(machines)
         if N == 0:
             return 0
         
         val_sum = sum(machines)
         if val_sum%N != 0:
             return -1
         
         val_each = val_sum//N
         
         go_left, go_right, net_change, max_step = 0, 0, 0, 0
         for i in range(N):
             go_left = -go_right
             go_right = go_right + machines[i] - val_each
             net_change = go_left + go_right
             step = max(abs(go_left), abs(go_right), net_change)
             max_step = max(max_step, step)
             
         return max_step