Minimize Circular Redistribution Cost
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given `n` warehouses arranged in a circle. `products[i]` is the number of products initially stored at warehouse `i`.
You may choose exactly one global movement direction for the entire redistribution: clockwise or counterclockwise. After the direction is chosen, every product may move only in that direction along adjacent edges of the circle. Moving one product across one edge costs `1`.
Your goal is to make every warehouse contain the same number of products. Return the minimum total movement cost over the two possible directions. If the total number of products cannot be evenly divided by `n`, return `-1`.
Implement:
`minRedistributionCost(products: int[]) -> long`
Example:
`products = [1, 11, 1, 1, 1]`
The average is `3`. Warehouse `1` has `8` extra products, and each of the other four warehouses needs `2` products. If all products move clockwise, the surplus must travel distances `1`, `2`, `3`, and `4`, two products per destination, for a total cost of:
`2 * (1 + 2 + 3 + 4) = 20`
The minimum cost is therefore `20`.
Assume `n` can be large, so the solution should run in linear time and use 64-bit arithmetic for the cost.
Quick Answer: This question evaluates algorithmic problem-solving skills in array manipulation, circular data structures, load balancing, and cost optimization while handling large inputs and 64-bit arithmetic.
You are given `n` warehouses arranged in a circle. `products[i]` is the number of products initially stored at warehouse `i`.
You must choose exactly one global movement direction for the entire redistribution: either clockwise or counterclockwise. After the direction is chosen, every product may move only in that direction along adjacent edges of the circle. Moving one product across one edge costs `1`.
Your goal is to make every warehouse contain the same number of products. Return the minimum total movement cost over the two possible directions. If the total number of products cannot be evenly divided by `n`, return `-1`.
A product may move across multiple edges, and each crossed edge adds `1` to the cost.
Constraints
- 1 <= n <= 2 * 10^5
- 0 <= products[i] <= 10^9
- Use 64-bit arithmetic for the total cost
Examples
Input: ([1, 11, 1, 1, 1],)
Expected Output: 20
Explanation: The total is 15, so each warehouse must end with 3. Warehouse 1 has 8 extra products, and the other four warehouses each need 2. In either direction, the cheapest valid redistribution costs 20.
Input: ([5, 0, 1],)
Expected Output: 4
Explanation: The total is 6, so the target is 2. Clockwise is cheaper: warehouse 0 sends 2 products to warehouse 1 (cost 2) and 1 product onward to warehouse 2 (additional cost 2), for a total of 4.
Input: ([1, 2, 4],)
Expected Output: -1
Explanation: The total number of products is 7, which cannot be evenly divided among 3 warehouses.
Input: ([7],)
Expected Output: 0
Explanation: There is only one warehouse, so it is already balanced.
Input: ([0, 0, 6],)
Expected Output: 6
Explanation: The target is 2. The warehouse with 6 products must send 2 products to each of the other warehouses. The minimum total distance traveled is 6.
Hints
- First compute the target number of products per warehouse. If the total is not divisible by `n`, the answer is immediately `-1`.
- For one fixed direction, think about how many products must cross each edge. A running prefix surplus determines these flows, and the best starting edge is related to the minimum prefix sum.