- array-rearrange, Arrays, Greedy, Mathematical, subarray

Minimum replacements required to make sum of all K-length subarrays equal

Given an array arr[] consisting of N positive integers and an integer K, the task is to make the sum of all K-length subarrays equal by replacing minimum number of array elements with any integer.Examples:Input: arr[] = {3, 4, 3, 5, 6}, K = 2Output: 2Explanation:Operation 1: Replacing arr[3] by 4 modiifes arr[] to {3, 4, 3, 4, 6}.Operation 2: Replacing arr[4] by 3 modifies arr[] to {3, 4, 3, 4, 3}.All subarrays of length 2 are {{3, 4}, {4, 3}, {3, 4}, {4, 3}}. Sum of all these subarrays is 7. Therefore, the minimum number of operations required is 2.Input: arr[] = {1, 2, 3, 1, 2}, K = 3Output: 0Explanation: All subarrays of length 3 are {{1, 2, 3}, {2, 3, 1}, {3, 1, 2}}. Since all these subarrays have sum 6, the number of operations required is 0.Approach: The idea is based on the observation that all subarrays will have equal sum, when all elements separated by distance K are equal. Therefore, the problem can be solved by counting the frequency of elements separated by a distance K and find the number which appears maximum times. Follow the steps below to solve the problem:Initialize a variable ans to store the required result.Iterate in the range [0, K-1] using the variable iCreate a map, freq to store the frequency of elements separated by a distance K starting from i.Traverse the map and find the element which occurs the maximum number of times.Again, traverse the map and if the element is not equal to the maximum occurring element then add its frequency to the ans.Print the value of ans as the result.Below is the implementation of the above approach:C++#include using namespace std;  void findMinOperations(int arr[],                       int N, int K){        int operations = 0;          for (int i = 0; i < K; i++) {                          unordered_map freq;          for (int j = i; j < N; j += K)            freq[arr[j]]++;                          int max1 = 0, num;                          for (auto x : freq) {            if (x.second > max1) {                max1 = x.second;                num = x.first;            }        }                  for (auto x : freq) {            if (x.first != num)                operations += x.second;        }    }          cout