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.

#2607

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

使子数组元素和相等

给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。你可以执行下述运算任意次：选中 arr 中任意一个元素，并使其值加上 1 或减去 1 。…

数组数学贪心排序数论

题目描述

给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。

你可以执行下述运算任意次：

选中 arr 中任意一个元素，并使其值加上 1 或减去 1 。

执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。

子数组 是数组的一个连续部分。

示例 1：

输入：arr = [1,4,1,3], k = 2
输出：1
解释：在下标为 1 的元素那里执行一次运算，使其等于 3 。
执行运算后，数组变为 [1,3,1,3] 。
- 0 处起始的子数组为 [1, 3] ，元素总和为 4 
- 1 处起始的子数组为 [3, 1] ，元素总和为 4 
- 2 处起始的子数组为 [1, 3] ，元素总和为 4 
- 3 处起始的子数组为 [3, 1] ，元素总和为 4

示例 2：

输入：arr = [2,5,5,7], k = 3
输出：5
解释：在下标为 0 的元素那里执行三次运算，使其等于 5 。在下标为 3 的元素那里执行两次运算，使其等于 5 。
执行运算后，数组变为 [5,5,5,5] 。
- 0 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 1 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 2 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 3 处起始的子数组为 [5, 5, 5] ，元素总和为 15

提示：

1 <= k <= arr.length <= 10⁵
1 <= arr[i] <= 10⁹

lightbulb

解题思路

方法一：数学（裴蜀定理） + 中位数贪心

题目要求每个长度为 $k$ 的子数组的元素总和相等，那么有以下等式成立：

arr_i + arr_{i + 1} + \cdots + arr_{i + k - 1} = arr_{i + 1} + arr_{i + 2} + \cdots + arr_{i + k}

化简得：

arr_i = arr_{i + k}

也即是说，数组 $arr$ 有一个大小为 $k$ 的循环节，而由于数组 $arr$ 是一个循环数组，那么数组 $arr$ 也有一个长度为 $n$ 的循环节。换句话说，数组 $arr$ 上间隔为 $k$ ，以及间隔为 $n$ 的元素均相等。即有：

arr_i = arr_{i + k \times x + n \times y}

根据裴蜀定理，有 $a \times x + b \times y = gcd(a, b)$ ，因此，有：

arr_i = arr_{i + k \times x + n \times y} = arr_{i + gcd(k, n)}

因此，数组 $arr$ 上的元素可以分为 $gcd(k, n)$ 组，每组的元素间隔为 $gcd(k, n)$ ，且每一组中的所有元素均相等。对于每一组，我们可以将其元素按照大小排序，然后取中位数，即可将该组中的所有元素变为中位数。对于所有组，我们将其中位数之差的绝对值求和，即为答案。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $arr$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:
        n = len(arr)
        g = gcd(n, k)
        ans = 0
        for i in range(g):
            t = sorted(arr[i:n:g])
            mid = t[len(t) >> 1]
            ans += sum(abs(x - mid) for x in t)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2818 操作使得分最大 #2601 质数减法运算 #2790 长度递增组的最大数目