An array of size N is given. In one operation we can add 1 to element at index i and subtract 1 from element at index j. (i!=j).
Using this operation we have to minimize the difference between maximum and minimum array elements and print minimum no. of operations required to achieve this minimum difference.
E.g. N=2, A=[1,6] -> Answer is 2.
Steps : [1,6] -> [2,5] -> [3,4] (This is minimum difference configuration that we can achieve]
E.g. N=5, A=[1,2,3,4,5]-> Answer is 3.
Steps : [1,2,3,4,5] -> [2,2,3,4,4] -> [3,2,3,4,3] -> [3,3,3,3,3] (This is minimum difference configuration].
Constraints :
N<=10^5, Array elements <= 10^4
I tried by taking the sum of elements and then taking the average and making each element equal to average but didn't work out. Then thought to apply binary search to find minimum possible difference value but couldn't come up with any good implementation regarding how to apply binary search here.
Please suggest some approach for solving this problem. Thanks in advance :)
Can you provide the problem link?? :) I have an idea but I just want to confirm that the idea is correct
Notice that the operation doesn't change the overal sum of elements. So first compute
S = a1 + a2 + ... + an.Notice that the smallest difference is obtained only if the final array consists of
S % ncopies ofceil(S / n)nubmer andn - S % ncopies offloor(S / n).It thus suffice to sort all the numbers, compute sum of absolute values of
floor(S / n) - aifor the firstn - S % nelements andceil(S / n) - aifor the lastS % nelements.Nice approach!! I have one query : Total number of increment/decrement operations should be equal right. So in this approach how is this part taken care of??
Since sum will still be the same before and after those changes therefore there has to be equal number additions and subtractions