Lakh's blog

Minimize the difference between smallest and largest element in array
By Lakh, history, 3 years ago, In English 
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 :)

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you provide the problem link?? :) I have an idea but I just want to confirm that the idea is correct

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 % n copies of ceil(S / n) nubmer and n - S % n copies of floor(S / n).

It thus suffice to sort all the numbers, compute sum of absolute values of floor(S / n) - ai for the first n - S % n elements and ceil(S / n) - ai for the last S % n elements.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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??

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Since sum will still be the same before and after those changes therefore there has to be equal number additions and subtractions

      → Reply