Make K-Subarray Sums Equal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
from math import gcd

class Solution:
    def makeSubKSumEqual(self, a: List[int], k: int) -> int:
        # Compute the greatest common divisor between the length of the array and k
        g = gcd(len(a), k)

        # Divide the array into sub-arrays based on the greatest common divisor
        sub_arrays = [sorted(a[i::g]) for i in range(g)]

        # Compute the median for each sub-array and calculate the sum of absolute differences
        result = sum(
            sum(abs(n - c[len(c) // 2]) for n in c)
            for c in sub_arrays
        )

        return result

Here’s the explanation for each step:

Computing the GCD: Using the gcd function, we find the greatest common divisor between the length of the array a and the given integer k.

Dividing into Sub-arrays: The array a is divided into sub-arrays based on the computed GCD, and each sub-array is sorted.

Calculating Absolute Differences: For each sub-array, the median is found (i.e., the middle element), and the sum of the absolute differences between each element and the median is computed.

Summing the Results: The total sum of the absolute differences is then computed and returned as the final result.