# 2607. Make K-Subarray Sums Equal
###### tags: `Leetcode` `Medium` `Math` `Greedy`
Link: https://leetcode.com/problems/make-k-subarray-sums-equal/description/
## 思路
Example 1: arr=[1,4,1,3], k=2, gcd(n,k)=gcd(4,2)=2
We need

arr[0]+arr[1]=arr[1]+arr[2] => arr[0]=arr[2]
arr[1]+arr[2]=arr[2]+arr[3] => arr[1]=arr[3]
arr[2]+arr[3]=arr[3]+arr[0] => arr[2]=arr[0]
arr[3]+arr[0]=arr[0]+arr[1] => arr[3]=arr[1]

Therefore ```arr[0]=arr[2]```, ```arr[1]=arr[3]```

Example 2: arr=[2,5,5,7], k=3, gcd(n,k)=gcd(4,3)=1

arr[0]+arr[1]+arr[2]=arr[1]+arr[2]+arr[3] => arr[0]=arr[3]
arr[1]+arr[2]+arr[3]=arr[2]+arr[3]+arr[0] => arr[1]=arr[0]
arr[2]+arr[3]+arr[0]=arr[3]+arr[0]+arr[1] => arr[2]=arr[1]
...

Therefore ```arr[0]=arr[1]=arr[2]=arr[3]```

Example 3: arr=[1,2,3,4,5,6], k=4, gcd(n,k)=gcd(6,4)=2

arr[0]+arr[1]+arr[2]+arr[3]=arr[1]+arr[2]+arr[3]+arr[4] => arr[0]=arr[4]
arr[1]+arr[2]+arr[3]+arr[4]=arr[2]+arr[3]+arr[4]+arr[5] => arr[1]=arr[5]
arr[2]+arr[3]+arr[4]+arr[5]=arr[3]+arr[4]+arr[5]+arr[0] => arr[2]=arr[0]
arr[3]+arr[4]+arr[5]+arr[0]=arr[4]+arr[5]+arr[0]+arr[1] => arr[3]=arr[1]
...

Therefore ```arr[0]=arr[2]=arr[4]```, ```arr[1]=arr[3]=arr[5]```
所以我们可以发现```arr[i]=arr[i+gcd]=arr[i+2*gcd]```
我们可以根据gcd给所有数字分组 分在一组的数字需要相等 那么最省operation的方法就是让他们都等于每组数字的中位数
## Code

class Solution:
    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:
        n = len(arr)
        gcd = math.gcd(n, k)
        ans = 0
        for i in range(gcd):
            tmp = sorted([arr[j] for j in range(i, n, gcd)])
            median = tmp[len(tmp)//2]
            ans += sum(abs(num-median) for num in tmp)
        return ans