FastPrep
Problem · Array

Minimum Redistribution Cost

Learn this problem
● MediumAmazonOA
See Amazon hiring insights

Problem statement

There are n warehouses arranged in a circle. Warehouse i initially stores products[i] items.

You may redistribute items around the circle, but all moved items must travel in one fixed direction: either clockwise or counter-clockwise. Moving one item across one edge costs 1.

Return the minimum total cost needed to make every warehouse contain the same number of products. You may choose the better of the two directions.

Function

getMinimumRedistributionCost(products: int[]) → long

Complete getMinimumRedistributionCost.

  • int products[n]: product counts around the circle

Returns

long: the minimum redistribution cost.

Examples

Example 1

products = [1,11,1,1,1]return = 20

The average is 3. The extra 8 products at the second warehouse must fill deficits of 2 at four other warehouses. In either direction, the total edge-crossing cost is 20.

Example 2

products = [0,6,0]return = 6

The average is 2. Four items move out of the middle warehouse: two cross one edge and two cross two edges.

Constraints

  • 1 <= products.length <= 10^5
  • 0 <= products[i] <= 10^9
  • The total number of products is divisible by products.length.

More Amazon problems

drafts saved locally
public long getMinimumRedistributionCost(int[] products) {
  // write your code here
}
products[1,11,1,1,1]
expected20
checking account