Минимизируйте количество целых чисел, которые нужно добавить в массив, чтобы сделать все соседние пары взаимно простыми.

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

Пример:

Input: N = 2, arr = [7, 42]
Output: 1
Explanation: After adding 11, the final array will be [7, 11, 42]. All adjacent elements are now coprime

Input: N = 4, arr = [2200, 42, 2184, 17]
Output: 3
Explanation: 43, 2195, 2199 can be added in the current array. The final sorted array will be [17, 42, 43, 2184, 2195, 2199, 2200] and all adjacent pairs are coprime.

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

• Отсортировать массив в порядке неубывания
• Выполните итерацию слева направо и проверьте каждую соседнюю пару на следующие условия:
• Если текущая пара взаимно проста, то нет необходимости добавлять дополнительный элемент.
• Если текущая пара не взаимно проста, то выполнить итерацию для всех значений между элементами и проверить, является ли текущее значение взаимно простым как с левой, так и с правой парами.
• В противном случае всегда можно добавить два взаимно простых значения друг с другом и с левым и правым значениями соответственно.

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

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