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

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

Code

[{"language":"C++","code":"class Solution {\npublic:\n    long long makeSubKSumEqual(vector<int>& arr, int k) {\n        int n = arr.size(), g = gcd(n, k);\n        long long ans = 0;\n        for (int i = 0; i < g; ++i) {\n            vector<int> vals;\n            for (int j = i; j < n; j += g) vals.push_back(arr[j]);\n            sort(vals.begin(), vals.end());\n            int m = vals.size();\n            int med = vals[m/2];\n            for (int v : vals) ans += abs(v - med);\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    long</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> long</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> makeSubKSumEqual</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> arr</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> k</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span>

Related Tags