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.

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

1. Create a recursive function of boolean to tell whether it is possible to sort an array by swapping only pairs with GCD as 1.
2. Iterate over all pairs of inversion:
   1. Check if their GCD is one or not.
   2. If its GCD is 1, then swap its element and recursively call for the remaining array.
   3. After that, backtrack the swap operation by swapping its element again.
3. 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;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

6
1, 9, 3, 7, 2, 4

Output:

Possible

Complexity Analysis

The time complexity of this approach is- O(N²*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