Минимизируйте значение данной функции для любого возможного значения X

Учитывая массив A[] , состоящий из N целых чисел ( индексация на основе 1 ), задача состоит в том, чтобы найти минимальное значение функции для любого возможного значения X .

Примеры:

Input: A[] = {1, 2, 3, 4}  
Output: 0
Explanation:
Consider the value of X as 0, then the value of the given function is (1 – 1 + 2 – 2 + 3 – 3 + 4 – 4) = 0, which is minimum.

Input: A[] = {5, 3, 9}
Output: 5

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

• Рассмотрим функцию как (B[i] = A[i] − i) , затем, чтобы минимизировать значение , идея состоит в том, чтобы выбрать значение X в качестве медианы массива B[] таким образом, чтобы сумма была минимизирована.

Следуйте инструкциям, чтобы решить проблему:

• Инициализируйте массив, скажем, B[] , который хранит значение (A[i] – i) для каждого возможного значения массива A[] .
• Пройдите по заданному массиву A[] и для каждого индекса i обновите значение B[i] как (A[i] – i) .
• Отсортируйте массив B[] в порядке возрастания и найдите значение X как медиану массива B[].
• После выполнения вышеуказанных действий найдите значение заданной функции для расчетного значения X .

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

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