Warehouse Allocation Moves
MediumGreedy · Amazon
boxes[i] is the number of boxes in pile i. In one move you take a single box off any pile and put it on any other pile.
Among all arrangements reachable this way, consider only those where the difference between the largest and the smallest pile is as small as possible. (With total boxes over n piles, that is a difference of 0 when total divides evenly by n, and 1 otherwise.)
Return the minimum number of moves needed to reach one of those most-balanced arrangements.
Example 1
- Input:
- boxes = [1, 2, 7]
- Output:
- 3
- Explanation
- Ten boxes over three piles cannot split evenly, so the best is a spread of 1: piles of 4, 3 and 3. Keeping the 4 on the pile that started at 7 means moving 3 boxes off it (two to the first pile, one to the second).
Example 2
- Input:
- boxes = [8, 8, 8, 3]
- Output:
- 3
- Explanation
- The 27 boxes settle as three piles of 7 and one of 6. Give the 7s to the three piles of 8 and the 6 to the pile of 3: each 8 gives away one box, for 3 moves.
Example 3
- Input:
- boxes = [6, 1, 6, 1]
- Output:
- 4
- Explanation
- The 14 boxes settle as two piles of 4 and two of 3. Each pile of 6 gives away 2 boxes, one to each pile of 1, for 4 moves.
Constraints
1 <= boxes.length <= 10^50 <= boxes[i] <= 10^9