2607. Make K-Subarray Sums Equal

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.

class Solution {
    long long uf[101010];
    long long find(long long u) {
        return uf[u] == u ? u : uf[u] = find(uf[u]);
    }
    void uni(long long u, long long v) {
        auto pu = find(u), pv = find(v);
        uf[pu] = uf[pv] = min(pu,pv);
    }
public:
    long long makeSubKSumEqual(vector<int>& arr, int k) {
        iota(begin(uf), end(uf) ,0);
        for(int i = 0; i < arr.size(); i++) uni(i, (i + k) % arr.size());
        unordered_map<long long, vector<int>> mp;
        for(int i = 0; i < arr.size(); i++) mp[find(i)].push_back(arr[i]);
        long long res = 0;
        for(auto& [k,vec] : mp) {
            sort(begin(vec), end(vec));
            long long med = vec[(vec.size() - 1) / 2];
            for(auto& v : vec) res += abs(v - med);
        }
        return res;
    }
};