Минимизируйте приращение или приращение и уменьшение пары, чтобы сделать все элементы массива равными

Учитывая массив arr[] размера N , задача состоит в том, чтобы минимизировать количество шагов, чтобы сделать все элементы массива равными, выполнив следующие операции:

1. Выберите элемент массива и увеличьте его на 1.
2. Выберите два элемента одновременно (arr[i], arr[j]), увеличьте arr[i] на 1 и уменьшите arr[j] на 1.

Примеры :

Input: arr = [4, 2, 4, 6]
Output: 2
Explanation: Do operation 2 on element 2 and 6 of the array. 
Hence increasing 2 by 2 and decreasing 6 by 2 makes all the elements of the array equal.

Input: arr = [1, 2, 3, 4]
Output: 3
Explanation: Increase 1 by 1 once. arr[] = {2, 2, 3, 4}.
Then increase 1 by 1 and decrease 4 by 1 in one step. arr[] = {3, 2, 3, 3}
Increase 2 by 1. arr[] = {3, 3, 3, 3}. So total operations = 3.

Подход: Эту проблему можно решить с помощью жадного подхода, основанного на следующей идее:

To minimize the number of steps make all of them equal to the ceil(average) of all array elements. To do this simultaneously increase the less elements and decrement the greater elements as long as possible and then increment the lesser elements only.

Выполните шаги, указанные ниже, чтобы решить проблему:

• Отсортируйте массив.
• Узнайте среднее значение массива (скажем, avg ).
• Теперь пройдите по массиву от i = 0 до N-1 :
  • Всякий раз, когда вы найдете любой элемент меньше среднего.
    • Пройдите от задней части массива и выведите элементы, которые больше среднего.
    • Наконец, добавьте к ответу avg-a[i] .
• Вернуть ответ.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N)
Вспомогательное пространство : O(1)