Минимальное увеличение или уменьшение на 1, необходимое для создания всех элементов массива в AP

Для заданного массива arr[] , состоящего из N целых чисел, задача состоит в том, чтобы найти минимальное количество приращений/уменьшений на 1, которое необходимо выполнить над элементами массива, чтобы все элементы заданного массива были arr[] в AP. Если невозможно составить массив в AP, то выведите «-1» .

Примеры:

Input: arr[] = {19, 16, 9, 5, 0}
Output: 3
Explanation:
Following are the order of increment/decrements of array elements is made:

1. Increment array element arr[0](= 19) by 1.
2. Decrement array element arr[1](= 16) by 1.
3. Increment array element arr[2](= 9) by 1.

After the above operations, the array arr[] modifies to {20, 15, 10, 5, 0}, which is in AP with first term 20 and common difference -5. Therefore, the total count of element is 3.

Input: arr[] = {1, 2, 3, 4, 10}
Output: -1

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

• Если N меньше 2 , то выведите 0 , потому что каждая такая последовательность является арифметической прогрессией.
• Инициализируйте переменную, скажем, res как N + 1 , чтобы сохранить ответ.
• Выполните итерацию в диапазоне [-1, 1], используя переменную a, и выполните следующие шаги:
  • Выполните итерацию в диапазоне [-1, 1], используя переменную b , и выполните следующие шаги:
    • Инициализируйте переменную say changes как 0 , чтобы сохранить количество измененных элементов массива arr[].
    • Если a не равно 0 , то увеличьте значение изменений на 1 .
    • Если b не равно 0 , то увеличьте значение изменений на 1 .
    • Инициализируйте переменную, скажем, orig как arr[0] + a, чтобы сохранить первый элемент, и diff как (arr[1] + b) – (arr[0] + a) , чтобы сохранить общую разность арифметической прогрессии.
    • Инициализируйте переменную, скажем, good as true , чтобы сохранить, возможна ли последовательность арифметической прогрессии с первым членом orig и общей разностью diff .
    • Выполните итерацию в диапазоне [2, N-1], используя переменную i , и выполните следующие шаги:
      • Инициализируйте фактическую переменную как orig+i*diff , чтобы сохранить фактический элемент арифметической прогрессии с индексом i .
      • Если abs(actual – arr[i]) больше 1 , то такая арифметическая прогрессия недостижима. Затем установите значение good на false и разорвите цикл.
      • В противном случае, если факт не равен arr[i], увеличьте значение изменений на 1 .
    • После прохождения внутреннего цикла for обновите значение res до min(changes, res).
• После выполнения вышеуказанных шагов, если res больше N , присвойте res -1. В противном случае выведите значение res в качестве ответа.

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

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