Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Problem Statement
Sample Examples
Implementation in C++
Complexity Analysis
Frequently Asked Questions
Key takeaways
Last Updated: Mar 27, 2024

Sort a Given Array by Swapping Only Pairs with GCD as 1

Author Ayush Tiwari
1 upvote
Create a resume that lands you SDE interviews at MAANG
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM


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



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



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


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. 


  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";
        cout << "Not Possible";
    return 0;



1, 9, 3, 7, 2, 4




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

Check out this problem - Count Inversions

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job

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. 

Recommended Problems - 

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!

Previous article
Power Set
Next article
Count of all unique paths from given source to destination in a Matrix
Live masterclass