Minimum Operations to Make K-Subarray Sums Equal in a Circular Array

You are given a 0-indexed integer array 'arr' and an integer 'k'. The array 'arr' is circular. This means the first element of the array is considered the next element of the last element, and vice versa. You can perform the following operation any number of times:

1. Pick any element from 'arr' and increase or decrease it by 1.

Your goal is to determine the minimum number of operations required to make the sum of each subarray of length 'k' equal.

Example:

Input:
arr = [1, 2, 3, 4, 5]
k = 3
Output: 3

Explanation:

• The original sums of the subarrays of length 3 are: [1+2+3=6], [2+3+4=9], [3+4+5=12], [4+5+1=10], [5+1+2=8].
• We can make the sums equal by increasing 'arr[0]' by 1, decreasing 'arr[2]' by 1, and decreasing 'arr[4]' by 1. This results in the sums: [2+2+3=7], [2+3+4=9], [3+4+4=11], [4+4+1=9], [5+1+2=8].

C++ Code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll makeSubKSumEqual(vector<int>& arr, int k) {
    int n = arr.size();
    vector<ll> prefixSum(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + arr[i];
    }
    ll ans = LLONG_MAX;
    for (int i = 0; i < k; i++) {
        ll sum = 0;
        for (int j = i; j < n; j += k) {
            sum += arr[j];
        }
        for (int j = 0; j < k; j++) {
            ll target = sum - (ll)j * (n + k) / k;
            ll curAns = 0;
            for (int l = j; l < n; l += k) {
                curAns += abs(target - prefixSum[l + 1] + prefixSum[j]);
            }
            ans = min(ans, curAns);
        }
    }
    return ans;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << makeSubKSumEqual(arr, k) << endl;
    return 0;
}

Explanation of the Code:

1. Prefix Sum: The code calculates the prefix sum of the array 'arr' to efficiently compute subarray sums. This avoids repeatedly calculating sums for each subarray.
2. Iterating through Subarrays: It iterates through all possible starting positions 'i' within the first 'k' elements. This ensures considering every possible subarray of length 'k'.
3. Target Sum: For each starting position 'i', it calculates the target sum 'target' that all subarrays of length 'k' should have. This target is derived from the total sum of the subarray starting at 'i' and distributed evenly among all subarrays of length 'k'.
4. Calculating Minimum Operations: For each potential target sum, it iterates through all possible starting positions 'j' for the subarrays of length 'k'. The code calculates the absolute difference between the target sum and the actual subarray sum starting at 'j', summing these differences for all subarrays. This sum represents the number of operations required to make the sum of the subarray starting at 'j' equal to the target sum. The minimum of these operation counts is then stored as 'ans'.

This code effectively computes the minimum operations needed to make the sums of all subarrays of length 'k' equal in a circular array. By using prefix sums and careful iteration strategies, it achieves an efficient and accurate solution.