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

Ayush Tiwari
Last Updated: May 13, 2022

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

  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;
}

 

Input:

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

 

Output:

Possible

Complexity Analysis

The time complexity of this approach is- O(N2*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 hereUntil then, Keep Learning and Keep Coding and practicing in Code studio.

Keep Learning, Keep Going.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think