Отсортируйте данный массив, поменяв местами только пары с GCD как 1

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

Пример:

Input: a = {3, 2, 1}
Output: Possible
Explanation: The given array can be sorted by swapping arr[0] and arr[2], i.e, 3 and 1 as gcd(3, 1) = 1. 

Input: arr[] = {10, 15, 6, 2, 9}
Output: Not Possible
Explanation: It is not possible to sort the given array using any sequence of valid operations.

Input: arr[] = {1, 9, 3, 7, 2, 4}
Output: Possible

Подход: Данную задачу можно решить с помощью рекурсии и поиска с возвратом. Создайте рекурсивную функцию для перебора всех инверсий данного массива, замените инвертированные элементы по одному, если их GCD равен 1, и рекурсивно вызовите оставшийся массив. В любой момент, если массив отсортирован, что можно проверить с помощью функции is_sorted(), вернуть true , иначе вернуть false .

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

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