Min Increment/Decrement operation to make all subarray sum of length k equal

Question

I am solving a problem where I have been given an array A of length N and an integer 0<K<N. We need to make sum of all subarrays(including circular) of length K equal in min operations. In one operation, we can either increment or decrement an element of array by 1.

I am unable to think of an algorithm to do this. For K=1, I can calculate the mean and then calculate the sum of absolute difference between mean and the array elements. But for larger K, can anybody give me a hint?

Answer 1

Hint: the final array should be whole repetitions of the first K elements, like [1,2,3,1,2,3,1,2,3] due to the circular constraint. Hence if N is not divisible by K, then all elements should be equal, and they should all be changed to the median of the array. If N is even, taking the N/2 or N/2+1 smallest element is the same. Otherwise, you need to make a[0], a[K], ... equal, a[1], a[K+1], ... equal and so on. Solve them independently by changing each to the corresponding median.