Minimize the difference between smallest and largest element in array

Revision en1, by Lakh, 2021-06-12 15:05:56
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 :)

Tags #array, minimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Lakh 2021-06-12 15:05:56 1133 Initial revision (published)