Minimum cost to make every Kth element in Array equal

By Ann Roberts On Mar 15, 2023

Given an array arr[] of integers and an integer K, the task is to find the minimum number of operations required to make every K^th element in the array equal. While performing one operation you can either increase a number by one or decrease the number by one.

Examples:

Input: arr[] = {1, 2, 3, 4, 4, 6}, K = 3
Output: 8
Explanation: For the given array, value of K = 3 which means every 3rd element in the array should be equal. So we have to make 1 = 4, 2 = 4 and 3 = 6. So by performing 3 operations on 1 we can make it equal to 4 (or vice versa it will take same number of operations) and 2 operations for making 2 and 4 equal and 3 operations to make 6 and 3 equal .So total number of operations is 8 which is the minimum cost to make every 3rd element in array equal.

Input: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, K = 3
Output: 24
Explanation: Value of K = 3, so every 3rd element should be equal which means we have to make 1 = 4 = 7 = 10, 2 = 5 = 8 and 3 = 6 = 9. For making 1 = 4 = 7 = 10, the minimum cost will be 12 and for making 2 = 5 = 8, the minimum cost will be 6 and for making 3 = 6 = 9, the minimum cost will be 6. So for making every 3rd element of array equal we have to perform minimum 24 operations.

Approach: To solve the problem follow the below idea:

We need to find average of every K^th element and then find difference between the K^th element and average.

This could be implemented by following below mentioned steps:

Initialize an array say average of size k for calculating the average of every K^th element.
Iterate over the input array and then calculate the average of every k^th element.
Initialize a variable say, minCost. Iterate over the input array and add the absolute difference of arr[i] and average[i%k], minCost += abs(arr[i] – average[i % k]).

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int findCost(vector<int> arr, int k)

{

int n = arr.size();

vector<int> average(k);

for (int i = 0; i < k; i++) {

average[i] = arr[i];

int total_ele = 1;

for (int j = i + k; j < n; j += k) {

average[i] = (average[i] + arr[j]);

total_ele++;

}

average[i] /= total_ele;

}

int minCost = 0;

for (int i = 0; i < n; i++) {

minCost += abs(arr[i] - average[i % k]);

}

return minCost;

}

int main()

{

vector<int> arr = { 1, 2, 3, 4, 4, 6 };

int k = 3;

cout << findCost(arr, k);

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(k) //For the array which was initialized for calculating the average.