# Sort a given Array by swapping only pairs with GCD as 1

## 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.

## 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).

## Frequently Asked Questions

**Q1. Which is Backtracking Algorithm? **

**Ans. **Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time.

**Q2. What is an application of recursion? **

**Ans.** Many well-known sorting algorithms (Quick sort, Merge sort, etc.) use recursion.

**Q3. What is the difference between ordered_set and unordered_set?**

**Ans. **Ordered_set using a red-black tree and unordered_set using the concept of hashing. Ordered stores the element in sorted order whereas unordered stores in random order.

## Key takeaways

This blog checks whether sorting a given array by swapping only pairs with GCD as 1 is possible or not.

We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem.

You can learn more about recursion and backtracking __here__. Until then, Keep Learning and Keep Coding and practicing in __Code studio__.

Keep Learning, Keep Going.

Happy Coding!

Comments

## No comments yet

## Be the first to share what you think