Make K-Subarray Sums Equal

Med

#2387Time: O(n * log(n/g)), where n is the array length and g = gcd(n, k). The GCD calculation is fast, O(log(min(n, k))). The main work is iterating through `g` groups. For each group of size `s = n/g`, sorting takes O(s log s). The total time for sorting all groups is `g * O((n/g) * log(n/g)) = O(n * log(n/g))`. In the worst case, `g=1`, and the complexity is O(n log n).Space: O(n/g), where g = gcd(n, k). We process one group at a time, and the size of each group is `n/g`. In the worst-case scenario (when `g=1`), the space complexity becomes O(n).1 company

Patterns

Math Greedy Number Theory

Algorithms

Sorting

Data structures

Array

Companies

Morgan Stanley

Prompt

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:

Pick any element from 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 <= 10⁵
1 <= arr[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

The core insight to solving this problem is understanding the condition required for all k-length subarray sums to be equal. If the sum of arr[i...i+k-1] must equal the sum of arr[i+1...i+k], then by canceling common terms, we find that arr[i] must equal arr[i+k] for all i (indices are modulo n). This property implies that elements whose indices are congruent modulo g = gcd(n, k) must all be made equal.

This partitions the array's elements into g independent groups. For each group, we have a set of numbers that we need to make equal by minimizing the total number of increment/decrement operations. The cost of changing a set of numbers {a_1, a_2, ..., a_m} to a single value x is sum(|a_j - x|). This sum is minimized when x is the median of the set.

This approach, therefore, involves iterating through each of the g groups, collecting its elements, sorting them to find the median, and then calculating the total operations required to change all elements in that group to their median.

Algorithm

Calculate the greatest common divisor g = gcd(arr.length, k).
Initialize a variable totalOps to 0 to store the total number of operations.
Iterate from i = 0 to g - 1. In each iteration, we process one of the g independent groups of elements.
- Create a temporary list to hold the elements of the current group.
- Iterate through the input array arr with a step of g, starting from index i. Add each element arr[j] (where j = i, i + g, i + 2g, ...) to the temporary list.
- Sort the temporary list in non-decreasing order.
- Find the median of the group. For a sorted list of size s, the median is the element at index s / 2.
- Calculate the cost for the current group. This is the sum of absolute differences between each element in the group and the median. Add this cost to totalOps.
After iterating through all g groups, return totalOps.

Walkthrough

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public long makeSubKSumEqual(int[] arr, int k) {7        int n = arr.length;8        // The number of independent groups is the gcd of n and k.9        int g = gcd(n, k);10        long totalOps = 0;11 12        // Process each of the g groups independently.13        for (int i = 0; i < g; i++) {14            List<Integer> group = new ArrayList<>();15            // Collect all elements for the current group.16            // Elements at indices i, i+g, i+2g, ... belong to the same group.17            for (int j = i; j < n; j += g) {18                group.add(arr[j]);19            }20            21            // To minimize sum of absolute differences, we need to make all elements22            // equal to the median of the group.23            // First, sort the group to find the median.24            Collections.sort(group);25            26            int median = group.get(group.size() / 2);27            28            // Calculate the cost for this group and add to the total.29            for (int val : group) {30                totalOps += Math.abs((long)val - median);31            }32        }33        34        return totalOps;35    }36 37    // Helper function to compute the greatest common divisor (GCD) using Euclidean algorithm.38    private int gcd(int a, int b) {39        while (b != 0) {40            int temp = b;41            b = a % b;42            a = temp;43        }44        return a;45    }46}

Complexity

Time

O(n * log(n/g)), where n is the array length and g = gcd(n, k). The GCD calculation is fast, O(log(min(n, k))). The main work is iterating through `g` groups. For each group of size `s = n/g`, sorting takes O(s log s). The total time for sorting all groups is `g * O((n/g) * log(n/g)) = O(n * log(n/g))`. In the worst case, `g=1`, and the complexity is O(n log n).

Space

O(n/g), where g = gcd(n, k). We process one group at a time, and the size of each group is `n/g`. In the worst-case scenario (when `g=1`), the space complexity becomes O(n).

Trade-offs

Pros

Correctly identifies the underlying mathematical structure of the problem.
The logic is relatively straightforward to understand and implement once the GCD insight is made.
It is efficient enough to pass within the time limits for the given constraints.

Cons

The time complexity is not optimal. The sorting step for each group can be improved upon.

This approach is an optimization of the previous one. The core logic remains the same: the problem is broken down into g = gcd(n, k) independent subproblems, and for each, we must find the median to minimize the operations. The bottleneck in the previous approach was finding the median by sorting, which takes O(s log s) time for a group of size s.

We can achieve a better time complexity by using a linear-time algorithm to find the median. The Quickselect algorithm, for instance, can find the k-th smallest element in an unsorted array in O(s) average time. By replacing the sorting step with Quickselect, we reduce the time to process each group from O(s log s) to O(s). This brings the overall time complexity of the solution down to O(n), which is optimal.

Algorithm

Calculate the greatest common divisor g = gcd(arr.length, k).
Initialize totalOps to 0.
Iterate from i = 0 to g - 1 to process each group.
- Collect all elements of the current group (indices i, i+g, ...) into a temporary list.
- Instead of sorting, use a linear-time selection algorithm like Quickselect to find the median of the list. The median is the k-th smallest element where k = list.size() / 2.
- Calculate the cost for the group by summing the absolute differences between each element and the found median.
- Add this group's cost to totalOps.
Return totalOps.

Walkthrough

1import java.util.ArrayList;2import java.util.List;3import java.util.Random;4 5class Solution {6    public long makeSubKSumEqual(int[] arr, int k) {7        int n = arr.length;8        int g = gcd(n, k);9        long totalOps = 0;10 11        for (int i = 0; i < g; i++) {12            List<Integer> group = new ArrayList<>();13            for (int j = i; j < n; j += g) {14                group.add(arr[j]);15            }16            17            // Find the median using Quickselect (find k-th smallest element)18            // which runs in O(group.size()) on average.19            int median = findKthSmallest(group, group.size() / 2);20            21            for (int val : group) {22                totalOps += Math.abs((long)val - median);23            }24        }25        26        return totalOps;27    }28 29    // Quickselect algorithm to find the k-th smallest element (0-indexed k)30    private int findKthSmallest(List<Integer> nums, int k) {31        int left = 0, right = nums.size() - 1;32        Random rand = new Random();33 34        while (left <= right) {35            // Using a random pivot helps to avoid worst-case O(n^2) behavior.36            int pivotIndex = partition(nums, left, right, rand.nextInt(right - left + 1) + left);37            if (pivotIndex == k) {38                return nums.get(pivotIndex);39            } else if (pivotIndex < k) {40                left = pivotIndex + 1;41            } else {42                right = pivotIndex - 1;43            }44        }45        return -1; // Should not be reached in a valid call46    }47 48    // Lomuto partition scheme for Quickselect49    private int partition(List<Integer> nums, int left, int right, int pivotIndex) {50        int pivotValue = nums.get(pivotIndex);51        swap(nums, pivotIndex, right); // Move pivot to the end52        int storeIndex = left;53        for (int i = left; i < right; i++) {54            if (nums.get(i) < pivotValue) {55                swap(nums, storeIndex, i);56                storeIndex++;57            }58        }59        swap(nums, right, storeIndex); // Move pivot to its final sorted position60        return storeIndex;61    }62 63    private void swap(List<Integer> nums, int i, int j) {64        int temp = nums.get(i);65        nums.set(i, nums.get(j));66        nums.set(j, temp);67    }68 69    private int gcd(int a, int b) {70        while (b != 0) {71            int temp = b;72            b = a % b;73            a = temp;74        }75        return a;76    }77}

Complexity

Time

O(n). The GCD calculation is negligible. We have `g` groups, each of size `s = n/g`. Finding the median for one group using Quickselect takes O(s) on average. The total time for all groups is `g * O(s) = g * O(n/g) = O(n)`. This is the dominant part of the algorithm.

Space

O(n/g), where g = gcd(n, k). The space is used to store the elements of one group at a time. The Quickselect algorithm is performed in-place on this list. The maximum space is O(n) when `g=1`.

Trade-offs

Pros

Achieves optimal time complexity.
Extremely efficient for very large inputs, as its runtime scales linearly with the input size.

Cons

The implementation of a linear-time selection algorithm like Quickselect is more complex than simply calling a built-in sort function.
A naive Quickselect implementation has a worst-case time complexity of O(n^2), although this is rare with good pivot selection strategies (like random pivot).

Solutions

Solution

1class Solution {2public3  long makeSubKSumEqual(int[] arr, int k) {4    int n = arr.length;5    int g = gcd(n, k);6    long ans = 0;7    for (int i = 0; i < g; ++i) {8      List<Integer> t = new ArrayList<>();9      for (int j = i; j < n; j += g) {10        t.add(arr[j]);11      }12      t.sort((a, b)->a - b);13      int mid = t.get(t.size() >> 1);14      for (int x : t) {15        ans += Math.abs(x - mid);16      }17    }18    return ans;19  }20private21  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }22}

1class Solution {2public:3  long long makeSubKSumEqual(vector<int> &arr, int k) {4    int n = arr.size();5    int g = gcd(n, k);6    long long ans = 0;7    for (int i = 0; i < g; ++i) {8      vector<int> t;9      for (int j = i; j < n; j += g) {10        t.push_back(arr[j]);11      }12      sort(t.begin(), t.end());13      int mid = t[t.size() / 2];14      for (int x : t) {15        ans += abs(x - mid);16      }17    }18    return ans;19  }20};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem