Make K-Subarray Sums Equal

Make K-Subarray Sums Equal

What is this problem about?

The Make K-Subarray Sums Equal problem provides a circular array and an integer k. You must ensure that the sum of every contiguous subarray of length k is exactly the same. You are allowed to increase or decrease any element by 1, which costs 1 operation. The goal is to find the minimum total cost to satisfy this condition.

Why is this asked in interviews?

This is a Hard-level problem that tests Number Theory and Median logic. It evaluates a candidate's ability to abstract a sliding window constraint into distinct, independent groups based on mathematical properties. It is a brilliant question to separate candidates who rely on brute-force simulation from those who understand cyclic dependencies and optimization via the median.

Algorithmic pattern used

This problem leverages Number Theory (GCD) and the Median Optimization pattern. Because the array is circular and sums of length k must be equal, arr[i] must equal arr[i + k]. Because of the circular nature, the actual cycle length of dependencies is GCD(n, k), where n is the array length. This means the array is partitioned into GCD(n, k) independent groups. To minimize the cost of making all elements in a group equal, you must change them all to the median value of that group.

Example explanation

Let array be [1, 4, 1, 3] with k = 2. Length n = 4. Cycles depend on GCD(4, 2) = 2. This means there are 2 independent groups.

• Group 0: indices 0, 2 -> values [1, 1].
  • Median of [1, 1] is 1. Cost to change them to 1 is $0 + 0 = 0$.
• Group 1: indices 1, 3 -> values [4, 3].
  • Median of [4, 3] is 3 (or 4). Let's pick 3. Cost to change 4 to 3 is 1. Cost to change 3 to 3 is 0. Total cost = 1. The total operations required is $0 + 1 = 1$. The array becomes [1, 3, 1, 3]. Subarrays of length 2 sum to 4.

Common mistakes candidates make

Candidates frequently fail to recognize the GCD(n, k) property and attempt to build adjacency lists to track which elements must be equal, leading to messy, slow graph traversals. Another major error is calculating the average (mean) of the groups instead of the median. Mathematically, to minimize absolute differences (L1 norm), you must always target the median, not the mean.

Interview preparation tip

For the Make K-Subarray Sums Equal interview pattern, remember two critical mathematical rules: 1) Cyclic arrays with a step k always form GCD(length, k) independent cycles. 2) The optimal target value to minimize absolute differences (|x - a| + |x - b|...) is always the median of those values. Sorting the group and picking the middle element is the key.