# Make K-Subarray Sums Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/make-k-subarray-sums-equal)
Canonical: https://scaleengineer.com/dsa/problems/make-k-subarray-sums-equal
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
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 <= 105`
* `1 <= arr[i] <= 109`

# Approaches
## Grouping by GCD and Sorting
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.
**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).
**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.
### Explanation
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public long makeSubKSumEqual(int[] arr, int k) {
        int n = arr.length;
        // The number of independent groups is the gcd of n and k.
        int g = gcd(n, k);
        long totalOps = 0;

        // Process each of the g groups independently.
        for (int i = 0; i < g; i++) {
            List<Integer> group = new ArrayList<>();
            // Collect all elements for the current group.
            // Elements at indices i, i+g, i+2g, ... belong to the same group.
            for (int j = i; j < n; j += g) {
                group.add(arr[j]);
            }
            
            // To minimize sum of absolute differences, we need to make all elements
            // equal to the median of the group.
            // First, sort the group to find the median.
            Collections.sort(group);
            
            int median = group.get(group.size() / 2);
            
            // Calculate the cost for this group and add to the total.
            for (int val : group) {
                totalOps += Math.abs((long)val - median);
            }
        }
        
        return totalOps;
    }

    // Helper function to compute the greatest common divisor (GCD) using Euclidean algorithm.
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### 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`.

## Optimized Grouping with Linear-Time Median Finding
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.
**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`.
**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).
### Explanation
```java
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    public long makeSubKSumEqual(int[] arr, int k) {
        int n = arr.length;
        int g = gcd(n, k);
        long totalOps = 0;

        for (int i = 0; i < g; i++) {
            List<Integer> group = new ArrayList<>();
            for (int j = i; j < n; j += g) {
                group.add(arr[j]);
            }
            
            // Find the median using Quickselect (find k-th smallest element)
            // which runs in O(group.size()) on average.
            int median = findKthSmallest(group, group.size() / 2);
            
            for (int val : group) {
                totalOps += Math.abs((long)val - median);
            }
        }
        
        return totalOps;
    }

    // Quickselect algorithm to find the k-th smallest element (0-indexed k)
    private int findKthSmallest(List<Integer> nums, int k) {
        int left = 0, right = nums.size() - 1;
        Random rand = new Random();

        while (left <= right) {
            // Using a random pivot helps to avoid worst-case O(n^2) behavior.
            int pivotIndex = partition(nums, left, right, rand.nextInt(right - left + 1) + left);
            if (pivotIndex == k) {
                return nums.get(pivotIndex);
            } else if (pivotIndex < k) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }
        return -1; // Should not be reached in a valid call
    }

    // Lomuto partition scheme for Quickselect
    private int partition(List<Integer> nums, int left, int right, int pivotIndex) {
        int pivotValue = nums.get(pivotIndex);
        swap(nums, pivotIndex, right); // Move pivot to the end
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums.get(i) < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, right, storeIndex); // Move pivot to its final sorted position
        return storeIndex;
    }

    private void swap(List<Integer> nums, int i, int j) {
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  long makeSubKSumEqual(int[] arr, int k) {
    int n = arr.length;
    int g = gcd(n, k);
    long ans = 0;
    for (int i = 0; i < g; ++i) {
      List<Integer> t = new ArrayList<>();
      for (int j = i; j < n; j += g) {
        t.add(arr[j]);
      }
      t.sort((a, b)->a - b);
      int mid = t.get(t.size() >> 1);
      for (int x : t) {
        ans += Math.abs(x - mid);
      }
    }
    return ans;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  long long makeSubKSumEqual(vector<int> &arr, int k) {
    int n = arr.size();
    int g = gcd(n, k);
    long long ans = 0;
    for (int i = 0; i < g; ++i) {
      vector<int> t;
      for (int j = i; j < n; j += g) {
        t.push_back(arr[j]);
      }
      sort(t.begin(), t.end());
      int mid = t[t.size() / 2];
      for (int x : t) {
        ans += abs(x - mid);
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```