So, I got this question in an online round of a company in hackerearth and i was passing only some test cases. Please help where im failing/ The answer to this question. Thanks in advance!
Question:
There is a circular array of size N. You have to divide the array into subarrays of size K. Let total number of subarrays you get after dividing the original array is Y. Your task is to make sum of all these subarrays equal (either by incrementing a number/decrementing a number) in the subarray. Print the minimum number of operations(increment/decrement) to make the sums equal.
Ex: N = 10, K = 1
arr = [1,2,3,4,5,6,7,8,9,10]
ans: 25
Explanation: Make all the elements in array to equal to 5. To do this, it takes 25 operations (min.)
Ex: N = 3 K=2
arr = [2,5,7]
ans: 6
Explanation: My subarrays are [2,5], [5,7], [7,2]
Current sum of each subarray is 7,13,11
if we make the sum of each subbarray to 11, then it takes min. steps (Since 11 is median). So ans is
11 - 7 = 4 (for 1st subarray)
13 - 11 = 2 (for 2nd subarray)
11 - 11 = 0 (for 3rd subarray)
Note: for 2nd subarray im doing (sum - med) because, an operation costs "1" irrespective of you increment or decrement.
My Approach:
calculate sums of all subarrays by brute force and store in vector.
sort the calculated sums and take the median.
take difference of sums and median, add all the differences and print.
Where I'm failing:
Ex: N =10, k=6
arr = [1,2,3,4,5,6,7,8,9,10]
(Sorry, Forgot the ans for this but my approach above mentioned was failing).