Минимальное количество замен реальными числами, необходимое для создания данного массива AP

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

Примеры:

Input: N = 6, arr[] = { 3, -2, 4, -1, -4, 0 }
Output: 3
Explanation: Change arr[0] = -2.5, arr[2] = -1.5, arr[4] = -0.5
So, the new sequence is AP { -2.5, -2, -1.5, -1, -0.5, 0} with 0.5 as the common difference.

Input: N = 5, arr[] = { 1, 0, 2, 4, 5}
Output: 2
Explanation: Change arr[1] = 2, arr[2] = 3
So, the new sequence is { 1, 2, 3, 4, 5 } which is an AP.

Подход: Решение задачи основано на нахождении всех возможных общих отличий от массива. Выполните шаги, указанные ниже:

• Запустите вложенный цикл , чтобы найти все возможные общие отличия от массива, где формируются только два элемента и AP, и сохраните их на карте .
• Теперь для каждого общего различия пройдитесь по массиву и найдите общее количество значений, лежащих в AP с этим конкретным различием.
• Оставшееся количество значений необходимо изменить.
• Минимум среди этих оставшихся значений и есть требуемый ответ.

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

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