Make K-Subarray Sums Equal

The key observation in Make K-Subarray Sums Equal is that equal sums for every circular length-k window force certain indices to end up with the same value. Those indices form disjoint cycles, and the cycle count is gcd(n, k). For each cycle, the minimum total change comes from moving every value to the median, then summing absolute differences across all cycles.

Problem Statement

You have a circular array arr and an integer k. You may increase or decrease any chosen element by 1 in one operation, and you want every subarray of length k, taken from every starting position around the circle, to have the same sum.

The hidden constraint is not about matching whole windows directly. When two consecutive length-k windows must have equal sums, the element leaving one window must match the element entering the next, which links positions spaced by k. The task is to use that invariant to compute the minimum total operations.

Examples

Example 1

Input: arr = [1,4,1,3], k = 2

Output: 1

we can do one operation on index 1 to make its value equal to 3. The array after the operation is [1,3,1,3]

• Subarray starts at index 0 is [1, 3], and its sum is 4
• Subarray starts at index 1 is [3, 1], and its sum is 4
• Subarray starts at index 2 is [1, 3], and its sum is 4
• Subarray starts at index 3 is [3, 1], and its sum is 4

Example 2

Input: arr = [2,5,5,7], k = 3

Output: 5

we can do three operations on index 0 to make its value equal to 5 and two operations on index 3 to make its value equal to 5. The array after the operations is [5,5,5,5]

• Subarray starts at index 0 is [5, 5, 5], and its sum is 15
• Subarray starts at index 1 is [5, 5, 5], and its sum is 15
• Subarray starts at index 2 is [5, 5, 5], and its sum is 15
• Subarray starts at index 3 is [5, 5, 5], and its sum is 15

Constraints

• 1 <= k <= arr.length <= 105
• 1 <= arr[i] <= 109

Solution Approach

Turn equal-window sums into equal-value cycles

If every circular subarray of length k has the same sum, then subtracting adjacent window sums shows arr[i] must equal arr[(i + k) % n]. Repeating that jump partitions the array into disjoint cycles. The number of cycles is gcd(n, k), and every index inside one cycle must be normalized to one common value.

Minimize each cycle independently with a median

Collect the values from one cycle, sort them, and choose the median as the target value. This is the greedy core of the problem: for absolute-distance cost, the median gives the minimum total number of +/-1 operations. Add the absolute differences from every value in the cycle to that median.

Sum the cycle costs for the final answer

Because cycles do not overlap, fixing one cycle never changes the requirement for another cycle. Iterate over the gcd(n, k) starting offsets, walk each cycle by repeated +k modulo n, compute its median cost, and add everything together. For arr = [1,4,1,3] and k = 2, the cycles are [1,1] and [4,3], so only the second cycle costs 1.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Let n be arr.length and g = gcd(n, k). The array splits into g cycles whose total size is n. Sorting the values inside each cycle dominates the runtime, so the total time is O(n log(n / g)) in aggregate and O(n log n) in the worst case. Extra space is O(n) if you store cycle values explicitly, or proportional to the largest cycle if you reuse a buffer.

What Interviewers Usually Probe

• The interviewer mentions gcd(n, k), which is the clue that circular jumps by k form repeated index cycles.
• They ask why equal k-window sums imply equality between specific elements, pushing you toward subtracting adjacent windows.
• They care about minimum operations after the groups are found, which usually means recognizing median, not average, for absolute-change cost.

Common Pitfalls or Variants

Common pitfalls

• Trying to equalize every length-k window directly with prefix sums misses the stronger invariant that linked positions must become equal.
• Using the mean for each cycle gives the wrong minimum because this problem charges absolute unit changes, so the median is optimal.
• Forgetting the circular structure or visiting indices twice can break cycle construction, especially when k and n are not coprime.

Follow-up variants

• Ask for the final transformed array instead of only the minimum cost, which means assigning each cycle to one chosen median value.
• Replace unit change cost with weighted change cost, which changes how you choose the best target inside each cycle.
• Remove the circular condition and use a linear array, where the adjacent-window invariant no longer creates the same modulo cycles.

FAQ

What is the main trick in Make K-Subarray Sums Equal?

Subtract neighboring circular length-k window sums. That gives arr[i] = arr[(i + k) % n], which turns the problem into fixing disjoint index cycles.

Why does gcd(n, k) matter here?

Jumping forward by k modulo n eventually repeats. The number of disjoint cycles created by that jump is gcd(n, k), and each cycle can be solved independently.

Why is the median the right greedy choice for each cycle?

Each operation changes a value by 1, so the cost for a chosen target is the sum of absolute differences. That sum is minimized by any median of the cycle values.

Can I use the average instead of the median?

No. The average minimizes squared error, not absolute unit-change cost. In this problem, choosing the average can produce a larger number of operations than choosing the median.

What should I store while implementing the cycle solution?

For each unprocessed cycle start from 0 to gcd(n, k) - 1, gather the values reached by repeated +k modulo n, sort that list, pick its median, and add absolute differences to the answer.