You are given a 0-indexed integer array arr and an integer k. The array arr is circular. In other words, the first element of the array is the next element of the last element, and the last element of the array is the previous element of the first element.
You can do the following operation any number of times:
arr and increase or decrease it by 1.Return the minimum number of operations such that the sum of each subarray of length k is equal.
A subarray is a contiguous part of the array.
Example 1:
Input: arr = [1,4,1,3], k = 2 Output: 1 Explanation: 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 Explanation: 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 <= 1051 <= arr[i] <= 109In #2607 Make K-Subarray Sums Equal, the key observation comes from how indices interact when repeatedly shifting by k. If the array length is n, indices connected through jumps of k form cycles determined by g = gcd(n, k). Elements within the same cycle must ultimately contribute consistently to maintain equal k-subarray sums.
Thus, we divide the array into g groups where each group contains indices reachable by repeatedly adding k modulo n. To minimize the number of operations needed to equalize values within a group, we use a classic trick: sort the group and convert all elements to the median, which minimizes the total absolute adjustment cost.
For each group, compute the total cost to move all values to the median and sum these costs across groups. Sorting each group dominates the runtime, leading to an efficient solution suitable for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| GCD-based grouping + median minimization | O(n log(n/g)) due to sorting groups | O(n) for storing grouped elements |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Think about gcd(n, k). How will it help to calculate the answer?
indices i and j are in the same group if gcd(n, k) mod i = gcd(n, k) mod j. Each group should have equal elements. Think about the minimum number of operations for each group
The minimum number of operations for each group equals the summation of differences between the elements and the median of elements inside the group.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
When minimizing the total sum of absolute differences in a set of numbers, the median gives the smallest possible cost. After grouping indices by their cycle, converting every value in the group to the median minimizes operations.
Problems like this are common in top tech interviews because they combine array manipulation with number theory insights such as GCD and cycle grouping. Understanding the pattern of index cycles is often the key interview takeaway.
The optimal approach uses number theory. Compute gcd(n, k) to form cyclic groups of indices and make all values within each group equal. The minimal cost is achieved by converting all elements in a group to the median value.
Arrays or dynamic lists are typically used to collect elements of each cycle group. Sorting these lists helps find the median efficiently, which is required to compute the minimum adjustment cost.