Problem Brief

Find Minimum Cost

NEW GRADOA

Amazon's warehouse management team is planning to roll out certain standards and checks that every Amazon Warehouse Manager will follow. Some products may need to be moved initially from one warehouse to another so that each warehouse complies.

A warehouse stores n identical containers arranged in the form of a circle. The distance between two adjacent containers is 1. Each container in a warehouse should hold the same number of products. Plan the optimal set of movements under the following rules.

Move products from any location in either the clockwise or the anti-clockwise direction. The direction must remain the same throughout the remaining moves.

While moving, collect excess products from some locations and deliver them to other locations that need more units.

The cost of each product transfer is the distance the product is moved.

The total cost is the sum of the costs for all products transferred.

Find the minimum cost such that finally, every container has the same number of products.

Note: In the examples, positions are one-indexed. It is guaranteed that it is always possible to distribute the products equally.

🍋‍🟩 Say TYVM to 🌟spike🌟 for the 1000 times! 🍉

1Example 1

Input

products = [3, 4, 6, 6, 6]

Output

Explanation

🌷 Option 1 - Start at the 3^rd position and move clockwise. Collect one product each from the 3^rd, 4^th, and 5^th positions. Transfer the products from: - the 5^th position to the 1^st position, the cost is 1 - the 4^th position to the 1^st position, the cost is 2 - the 3^rd position to the 2^nd position, the cost is 4 Now each container has 5 units and the total cost is 1 + 2 + 4 = 7. 🌷 Option 2 - Start at the 5^th position and move anti-clockwise. Collect one product each from the 5^th, 4^th, and 3^rd positions. Transfer the products from: - the 3^rd position to the 1^st position, the cost is 2 - the 4^th position to the 1^st position, the cost is 3 - the 5^th position to the 2^nd position, the cost is 3 Now each container has 5 units and the total cost is 2 + 3 + 3 = 8.

Constraints

Limits and guarantees your solution can rely on.

🌺🌺