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

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

Примеры :

Input: N = 5, arr[] = {13, 6, 11, 18, 4}
Output: 15
Explanation: Convert 4 to 9, 8 to 10, 13 to12 and 18to13, the new array becomes {9, 10, 11, 12, 13}. 
So the sum of changes are abs(9-4) + abs(10-8) + abs(12-13) + abs(13-18) = 15.

Input: N = 2, arr[] = {3, 8}
Output: 4

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

• Сортировать массив
• Возьмите переменную mid , в которой хранится медиана массива, и переменную pos , в которой хранится ее позиция.
• Кроме того, возьмите переменную ele и инициализируйте ее с помощью в наименьшее значение результирующего массива т.е. (mid – pos) и переменная sum = 0 для хранения суммы всех возможных изменений элементов массива.
• Итерация по массиву и в каждой i -й итерации:
  • Увеличение суммы с помощью abs(arr[i]-ele) (добавление разницы между исходным и требуемым элементом)
  • Увеличить ele на 1
• Выведите сумму.

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

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