Максимизируйте K, чтобы сделать данный массив палиндромом, когда каждый элемент заменяется его остатком с K

Дан массив A[] , содержащий N положительных целых чисел, задача состоит в том, чтобы найти максимально возможное число K , такое что после замены всех элементов на элементы по модулю K(A[i]=A[i]%K для всех 0< =i<N), массив становится палиндромом. Если K бесконечно велико, выведите -1.

Примеры:

Input: A={1, 2, 3, 4}, N=4
Output:
1
Explanation:
For K=1, A becomes {1%1, 2%1, 3%1, 4%1}={0, 0, 0, 0} which is a palindromic array. 

Input: A={1, 2, 3, 2, 1}, N=5
Output:
-1

Наблюдение: В решении задачи помогают следующие наблюдения:

1. Если массив уже является палиндромом, K может быть бесконечно большим.
2. Два числа, скажем, A и B , можно сделать равными, взяв их модуль с их разностью (|AB|) , а также коэффициенты их разности.

Подход: проблему можно решить, приравняв K к НОД. абсолютных разностей A[i] и A[Ni-1]. Выполните следующие шаги, чтобы решить проблему:

1. Проверьте, является ли A уже палиндромом. Если это так, верните -1 .
2. Сохраните абсолютную разницу между первым и последним элементами массива в переменной, скажем, K , которая будет хранить наибольшее число, необходимое для преобразования A в палиндром.
3. Перейдите от 1 к N/2-1 и для каждого текущего индекса i сделайте следующее:
   1. Обновите K с помощью GCD K и абсолютной разности A[i] и A[Ni-1].
4. Вернуть К.

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

Временная сложность: O(NLogM), где M — самый большой элемент в массиве.
Вспомогательное пространство: O(1)