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

Дан массив arr[] ( индексация на основе 1 ), состоящий из N целых чисел, задача состоит в том, чтобы найти минимальную сумму абсолютной разницы между всеми парами элементов массива путем уменьшения и увеличения любой пары элементов на 1 любое количество раз.

Примеры:

Input: arr[] = {1, 2, 3}
Output: 0
Explanation:
Modify the array elements by  performing the following operations:

• Choose the pairs of element (arr[1], arr[3]) and incrementing and decrementing the pairs modifies the array to {2, 2, 2}.

After the above operations, the sum of the absolute differences is  |2 – 2| + |2 – 2| + |2 – 2| = 0. Therefore, print 0.

Input: arr[] = {0, 1, 0, 1}
Output: 4

Подход: Данную проблему можно решить с помощью жадного подхода. Можно заметить, что для минимизации суммы абсолютной разницы между каждой парой элементов массива arr[] идея сделать каждый элемент массива закрытым друг для друга. Выполните следующие шаги, чтобы решить проблему:

• Найдите сумму элементов массива arr[] и сохраните ее в переменной, скажем, sum .
• Теперь, если значение суммы % N равно 0 , тогда выведите 0 , поскольку все элементы массива можно сделать равными, а результирующее значение выражения всегда равно 0 . В противном случае найдите значение суммы % N и сохраните его в переменной, скажем, R .
• Теперь, если все элементы массива равны sum/N , тогда мы можем сделать R элементов массива равным 1 , а остальные элементы массива равными 0 , чтобы минимизировать результирующее значение.
• После вышеуказанных шагов минимальная сумма абсолютной разницы определяется как R*(N – R) .

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

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