All problems

Shelf Rebalancing

Medium · prefix sum

A shop has a row of shelves. Shelf i holds stock[i] items. The shopkeeper wants every shelf to hold the same number of items.

In one move the shopkeeper takes one item from a shelf and puts it on the shelf directly next to it, on the left or on the right. An item can be passed along the row, so taking one item three shelves along takes three moves.

The total number of items is always divisible by the number of shelves, so an even split exists. Return the fewest moves needed to give every shelf the same number of items.

Examples

Example 1

Input: stock = [5, 1, 3]

Output: 2

Every shelf should hold 3 items. Move two items from the first shelf to the second one, giving [3, 3, 3].

Example 2

Input: stock = [0, 0, 6]

Output: 6

Every shelf should hold 2 items. Two items go from the last shelf to the middle one (2 moves) and two more travel all the way to the first shelf (2 moves each, 4 in total).

Example 3

Input: stock = [4, 4]

Output: 0

The shelves are already equal.

Constraints

• 1 <= len(stock) <= 500
• 0 <= stock[i] <= 100
• The sum of stock is divisible by len(stock).