Блог пользователя Lakh

Автор Lakh, история, 3 года назад, По-английски
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 :)

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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