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 eachsubarray of length _k is equal.

A subarray is a contiguous part of the array.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7
8

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^5
  • 1 <= arr[i] <= 10^9

Solution

Method 1 – Grouping by GCD and Median Minimization

Intuition

The key is that for all subarrays of length k to have equal sum in a circular array, elements at positions with the same index modulo gcd(n, k) must be made equal. For each group, the minimum number of operations is achieved by making all elements equal to the median of the group.

Approach

  1. Compute g = gcd(n, k), where n is the length of arr.
  2. For each group of indices i, i+g, i+2g, ..., collect the values.
  3. For each group, sort the values and find the median.
  4. The minimum number of operations for the group is the sum of absolute differences to the median.
  5. Sum the operations for all groups and return the total.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

func gcd(a, b int) int { for b != 0 { a, b = b, a%b }; return a }
func makeSubKSumEqual(arr []int, k int) int64 {
    n, g := len(arr), gcd(len(arr), k)
    var ans int64
    for i := 0; i < g; i++ {
        vals := []int{}
        for j := i; j < n; j += g {
            vals = append(vals, arr[j])
        }
        sort.Ints(vals)
        m := len(vals)
        med := vals[m/2]
        for _, v := range vals {
            ans += int64(abs(v - med))
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;
class Solution {
    public long makeSubKSumEqual(int[] arr, int k) {
        int n = arr.length, g = gcd(n, k);
        long ans = 0;
        for (int i = 0; i < g; ++i) {
            List<Integer> vals = new ArrayList<>();
            for (int j = i; j < n; j += g) vals.add(arr[j]);
            Collections.sort(vals);
            int m = vals.size(), med = vals.get(m/2);
            for (int v : vals) ans += Math.abs(v - med);
        }
        return ans;
    }
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
        val n = arr.size
        val g = gcd(n, k)
        var ans = 0L
        for (i in 0 until g) {
            val vals = mutableListOf<Int>()
            for (j in i until n step g) vals.add(arr[j])
            vals.sort()
            val med = vals[vals.size/2]
            for (v in vals) ans += kotlin.math.abs(v - med)
        }
        return ans
    }
    fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from math import gcd
class Solution:
    def makeSubKSumEqual(self, arr: list[int], k: int) -> int:
        n, g = len(arr), gcd(len(arr), k)
        ans = 0
        for i in range(g):
            vals = [arr[j] for j in range(i, n, g)]
            vals.sort()
            med = vals[len(vals)//2]
            ans += sum(abs(v - med) for v in vals)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn make_sub_k_sum_equal(arr: Vec<i32>, k: i32) -> i64 {
        fn gcd(mut a: i32, mut b: i32) -> i32 { while b != 0 { let t = b; b = a % b; a = t; } a }
        let n = arr.len();
        let g = gcd(n as i32, k) as usize;
        let mut ans = 0i64;
        for i in 0..g {
            let mut vals = vec![];
            let mut j = i;
            while j < n {
                vals.push(arr[j]);
                j += g;
            }
            vals.sort();
            let med = vals[vals.len()/2];
            for v in vals { ans += (v - med).abs() as i64; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    makeSubKSumEqual(arr: number[], k: number): number {
        function gcd(a: number, b: number): number { while (b) [a, b] = [b, a % b]; return a; }
        const n = arr.length, g = gcd(n, k);
        let ans = 0;
        for (let i = 0; i < g; ++i) {
            const vals: number[] = [];
            for (let j = i; j < n; j += g) vals.push(arr[j]);
            vals.sort((a, b) => a - b);
            const med = vals[Math.floor(vals.length/2)];
            for (const v of vals) ans += Math.abs(v - med);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), as each group is sorted.
  • 🧺 Space complexity: O(n), for storing groups.