Наибольшее число для создания данного массива путем добавления или вычитания K несколько раз

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

Примеры:

Input: K = 5, N = 3, arr = {3, 7, 13}
Output: 2
Explanation: As currently K is 5 we can subtract 2 to get 3 now K become 3.
After this we will add two times 2 in 3 to form 7. Now K is 7.
After this we will add 2 three times to form 13.

Input: K = 6, N = 3, arr = {11, 6, 2}
Output: 1

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

To get the maximum value, we must select the highest value which is a factor of the differences of K with all the array elements, i.e., the GCD of the differences of all the array elements with K.

Выполните следующие шаги, чтобы решить эту проблему:

• Сохраните разницу всех элементов массива из K в массиве (скажем, temp[] ).
• Перебрать массив arr[] :
  • Сохраните абсолютную разницу между K и текущим элементом массива в temp[] .
• Инициализируйте переменную (например, ans = 0 ), чтобы сохранить ответ.
• Итерация по temp[]:
  • Обновите ответ с помощью GCD ans и текущего значения элемента temp[] .
• Вернуть значение ans в качестве требуемого ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * logD), где D — максимальная разница элемента массива с K.
Вспомогательное пространство: O(N)