Problem · Array

Warehouse Allocation (Distribute)

EasyAmazonINTERNOA
See Amazon hiring insights

Amazon has a warehouse that stores piles of boxes containing goods to be shipped. There are n piles numbered 1, 2, ..., n, where the i-th pile has boxes[i] boxes.

To achieve an even distribution of boxes, the caretaker can perform the following operation any number of times (possibly zero):

  • Choose two distinct piles i and j such that boxes[i] > 0.
  • Remove one box from pile i and place it on pile j (increment boxes[j] by 1 and decrement boxes[i] by 1).

The caretaker wishes to minimize the difference between the maximum and the minimum number of boxes among the piles. Call this minimum achievable difference d.

Complete the function findMinimumOperations, which returns the minimum number of operations required to reach a configuration whose difference between the maximum and minimum number of boxes equals d.

Examples
01 · Example 1
boxes = [5, 5, 8, 7]
return = 2
Example 1 illustration
Consider the number of piles to be n = 4 and the boxes in them are boxes = [5, 5, 8, 7]. The minimum possible difference that can be achieved is 1 by transforming the piles into [6, 6, 7, 6] as below. Hence the answer is 2.
02 · Example 2
boxes = [2, 4, 1]
return = 1
Move a box from pile 2 to pile 3: [2, 4, 1] -> [2, 3, 2]
03 · Example 3
boxes = [4, 4, 4, 4, 4]
return = 0
Constraints
  • 1 <= n <= 105
  • 1 <= boxes[i] <= 109
More Amazon problems
drafts saved locally
public long findMinimumOperations(int[] boxes) {
  // write your code here
}
boxes[5, 5, 8, 7]
expected2
sign in to submit