Introduction
This blog introduces you to the problem of whether sorting a given array by swapping only pairs with GCD as one is possible or not.
Problem Statement
The problem states that you are given an array a[] of length n, we have to check whether it is possible to sort the given array by swapping only pairs with gcd as 1 using any number of operations where at each operation we have two indexes i and j we can swap its element if GCD or a[i] and a[j] is 1
Sample Examples
So before we deep dive into the solution to this problem, we should first look at some examples to understand the problem better.
Example  1
Given Array [3 2 1]
Output  possible
Explanation:
We can swap a[0] and a[2] because the GCD of 3 and 2 is 1. Our resultant array look like 1 2 3.
Example  2
Given Array [4 2 6 20]
Output  Not possible
Explanation:
We cannot sort a given array by swapping only pairs with GCD as 1 because there is no one whose GCD is 1.
Recommended topic, kth largest element in an array, and Euclid GCD Algorithm
Approach
In this problem, we have to check whether sorting a given array by swapping only pairs with GCD as 1 is possible or not. The only prerequisite of this problem is recursion and backtracking. First of all, we have to think about if the inversion count of the array is greater than 0, then the array is unsorted. If we make the inversion count of the array is zero, then our array becomes sorted. So, for every pair of inversions, swap the inverted element and recursively call the remaining array. If at any point our array became sorted, then return true otherwise, we have to return false.
Algorithm
 Create a recursive function of boolean to tell whether it is possible to sort an array by swapping only pairs with GCD as 1.

Iterate over all pairs of inversion:
 Check if their GCD is one or not.
 If its GCD is 1, then swap its element and recursively call for the remaining array.
 After that, backtrack the swap operation by swapping its element again.
 If any point check array is sorted by another function, return true otherwise false.
Implementation in C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// function to check array is sorted
bool array_sorted(vector < int > & a, int n) {
for (int i = 1; i < n; i++) {
if (a[i] < a[i  1])
return false;
}
return true;
}
// function to check whether sorting a given array by swapping only pairs with GCD as 1 is possible or not
bool recursive(vector < int > & a, int n) {
// If the array is sorted or not
if (array_sorted(a, n)) {
return true;
}
//store the result
bool ans = false;
// traverse to all possible inversion
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// check the pair is inversion or not
if (a[i] > a[j]) {
// find GCD of pair a[i] and a[j]
int GCD = __gcd(a[i], a[j]);
if (GCD == 1) {
// swap the element
swap(a[i], a[j]);
// recusively call remaining function
ans = (ans  recursive(a, n));
// Backtrack the swapping
swap(a[i], a[j]);
}
}
}
}
// Return Answer
return ans;
}
// Driver Code
int main() {
int n = 6;
vector < int > a = { 1, 9, 3, 7, 2, 4 };
if (recursive(a, n))
cout << "Possible";
else
cout << "Not Possible";
return 0;
}
Input:
6
1, 9, 3, 7, 2, 4
Output:
Possible
Complexity Analysis
The time complexity of this approach is O(N^{2}*N!). In the worst case, we have to check on inversion in every permutation.
The space complexity of this approach is O(1).
Check out this problem  Count Inversions