Show problems as
Classic problem #2607MediumArrayMathGreedySortingNumber Theory

Make K-Subarray Sums Equal

Real-world version: Balancing the Carousel Sweeps
Tracked in this browser only
Read Make K-Subarray Sums Equal on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A carousel carries n trays bolted in a ring and numbered 0 through n - 1, where n is the length of loads. Tray i holds loads[i] grams of grain, and tray n - 1 sits immediately before tray 0, so the numbering closes up into a circle.

A sweep is span trays taken one after another around the ring: it begins at some tray, steps to the next tray each time, and carries on past tray n - 1 onto tray 0 if it has not finished yet. There are n sweeps, one beginning at each tray.

The carousel is balanced when all n sweeps hold the same weight of grain. One adjustment either adds a gram to a single tray or takes a gram off a single tray. Return the fewest adjustments that leave the carousel balanced. A tray may be brought to any whole number of grams, including zero.

Examples

Example 1

Input
loads = [5, 1, 2, 8, 4, 3], span = 4
Output
10

Bringing the trays to 4, 3, 4, 3, 4, 3 grams takes 1 + 2 + 2 + 5 + 0 + 0 = 10 adjustments, and every sweep of four trays then holds 14 grams.

Example 2

Input
loads = [4, 1, 9, 4], span = 2
Output
8

Bringing the trays to 9, 4, 9, 4 grams takes 5 + 3 + 0 + 0 = 8 adjustments, and each of the four sweeps of two trays then holds 13 grams.

Example 3

Input
loads = [6, 6, 6, 6], span = 2
Output
0

Every sweep of two trays already holds 12 grams, so nothing has to be adjusted.

Constraints

  • 1 <= span <= loads.length <= 10^5
  • 1 <= loads[i] <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_adjustments(loads: list[int], span: int) -> int:
Java
public long minAdjustments(int[] loads, int span)

More on the same topics