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].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Greedy algorithms

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

Solutions:
class Solution:

	def findMinMoves(self, machines):
		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):
		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
			result = max(result, abs(target - cum), max_share)
		return result


class Solution:

	def findMinMoves(self, machines):
		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):
		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):
		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):
		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
			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


class Solution:

	def __init__(self):
		pass

	def findMinMoves(self, machines):
		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