Максимизируйте размер прыжка, чтобы достичь всех заданных точек из заданной начальной точки.
Дан массив arr[] , состоящий из N целых чисел, представляющих координаты в числовой строке, и целое число S. Найдите максимальный размер прыжка, необходимый для посещения всех координат хотя бы один раз, если начальная позиция S . Кроме того, разрешены прыжки в обе стороны.
Пример:
Input: arr[]={1, 7, 3, 9, 5, 11}, S=3
Output: 2
Explanation: Jumps of size 2 is able to visit all the coordinates on the line, in the following way:
Jump -2: Reach 1 from 3.
Jump +2: Reach 3 from 1.
Jump +2: Reach 5 from 3.
Jump +2: Reach 7 from 5.
Jump +2: Reach 9 from 7.
Jump +2: Reach 11 from 9.Input: arr[]={33, 105, 57}, S=81
Output: 24
Подход: После прочтения задачи можно сделать наблюдение, что наибольший общий делитель всех разностей между двумя соседними точками на прямой является максимальным размером прыжка, необходимого для посещения всех точек. Итак, чтобы решить эту проблему, выполните следующие действия:
- Вставьте S в массив arr и отсортируйте его.
- Найдите НОД между разностями всех соседних пар в массиве arr .
- Верните окончательный gcd в качестве ответа на эту проблему.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(NlogN)
Вспомогательное пространство: O(1).