Given an array arr[], the task is to check if it is possible to sort the given array using any number of operations where at each operation, two elements arr[i] and arr[j] can be swapped if GCD of arr[i] and arr[j] is 1.
Example:
Input: a = {3, 2, 1}
Output: Possible
Explanation: The given array can be sorted by swapping arr[0] and arr[2], i.e, 3 and 1 as gcd(3, 1) = 1.Input: arr[] = {10, 15, 6, 2, 9}
Output: Not Possible
Explanation: It is not possible to sort the given array using any sequence of valid operations.Input: arr[] = {1, 9, 3, 7, 2, 4}
Output: Possible
Approach: The given problem can be solved with the help of recursion and backtracking. Create a recursive function to iterate over all inversions of the given array, swap the inverted elements one at a time if their GCD is 1 and recursively call for the remaining array. At any point, if the array is sorted which can be checked using the is_sorted() function, return true otherwise, return false.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Recursive function to check if it is// possible to sort the given array by// swapping elements with their GCD = 1bool isPossible(vector<int> arr){ // If the given array is sorted if (is_sorted(arr.begin(), arr.end())) { return true; } // Stores if it is possible to sort // the given array bool res = false; // Iterate for all possible pairs of // Inversions for (int i = 0; i < arr.size(); i++) { for (int j = i + 1; j < arr.size(); j++) { // If for current inversion, // GCD of both elements is 1, // GCD of both the indices if (arr[i] > arr[j] && __gcd(arr[i], arr[j]) == 1) { swap(arr[i], arr[j]); // Recursive Call for the // remaining array res = (res | isPossible(arr)); // Backtrack swap(arr[i], arr[j]); } } } // Return Answer return res;}// Driver Codeint main(){ vector<int> arr = { 1, 9, 3, 7, 2, 4 }; if (isPossible(arr)) cout << "Possible"; else cout << "Not Possible"; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Recursive function to check if it is// possible to sort the given array by// swapping elements with their GCD = 1static boolean isPossible(int[] arr){ // If the given array is sorted if (is_sorted(arr)) { return true; } // Stores if it is possible to sort // the given array boolean res = false; // Iterate for all possible pairs of // Inversions for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { // If for current inversion, // GCD of both elements is 1, // GCD of both the indices if (arr[i] > arr[j] && __gcd(arr[i], arr[j]) == 1) { arr = swap(arr,i,j); // Recursive Call for the // remaining array res = (res | isPossible(arr)); // Backtrack arr = swap(arr,i,j); } } } // Return Answer return res;}static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); }static int[] swap(int []arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr;}private static boolean is_sorted(int[] a) { int i; for(i = 0; i < a.length - 1 && a[i] < a[i+1]; i++){} return (i == a.length - 1);}public static void main(String[] args){ int[] arr = { 1, 9, 3, 7, 2, 4 }; if (isPossible(arr)) System.out.print("Possible"); else System.out.print("Not Possible");}}// This code is contributed by shikhasingrajput |
Python3
# Python code for the above approach# Recursive function to return gcd of a and bdef __gcd(a, b): # Everything divides 0 if (a == 0): return b if (b == 0): return a # base case if (a == b): return a # a is greater if (a > b): return __gcd(a - b, b) return __gcd(a, b - a)# Recursive function to check if it is# possible to sort the given array by# swapping elements with their GCD = 1def isPossible(arr): # If the given array is sorted brr = sorted(arr) if (arr == brr): return True # Stores if it is possible to sort # the given array res = False # Iterate for all possible pairs of # Inversions for i in range(len(arr)): for j in range(i + 1, len(arr)): # If for current inversion, # GCD of both elements is 1, # GCD of both the indices if (arr[i] > arr[j] and __gcd(arr[i], arr[j]) == 1): temp = arr[i] arr[i] = arr[j] arr[j] = temp # Recursive Call for the # remaining array res = (res | isPossible(arr)) # Backtrack temp = arr[i] arr[i] = arr[j] arr[j] = temp # Return Answer return res# Driver Codearr = [1, 9, 3, 7, 2, 4]if (isPossible(arr)): print("Possible")else: print("Not Possible")# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;public class GFG{// Recursive function to check if it is// possible to sort the given array by// swapping elements with their GCD = 1static bool isPossible(int[] arr){ // If the given array is sorted if (is_sorted(arr)) { return true; } // Stores if it is possible to sort // the given array bool res = false; // Iterate for all possible pairs of // Inversions for (int i = 0; i < arr.Length; i++) { for (int j = i + 1; j < arr.Length; j++) { // If for current inversion, // GCD of both elements is 1, // GCD of both the indices if (arr[i] > arr[j] && __gcd(arr[i], arr[j]) == 1) { arr = swap(arr,i,j); // Recursive Call for the // remaining array res = (res | isPossible(arr)); // Backtrack arr = swap(arr,i,j); } } } // Return Answer return res;}static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); }static int[] swap(int []arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr;}private static bool is_sorted(int[] a) { int i; for(i = 0; i < a.Length - 1 && a[i] < a[i+1]; i++){} return (i == a.Length - 1);}public static void Main(String[] args){ int[] arr = { 1, 9, 3, 7, 2, 4 }; if (isPossible(arr)) Console.Write("Possible"); else Console.Write("Not Possible");}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Recursive function to return gcd of a and b function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Recursive function to check if it is // possible to sort the given array by // swapping elements with their GCD = 1 function isPossible(arr) { // If the given array is sorted brr = arr.sort(function (a, b) { return a - b }) if (arr == brr) { return true; } // Stores if it is possible to sort // the given array let res = false; // Iterate for all possible pairs of // Inversions for (let i = 0; i < arr.length; i++) { for (let j = i + 1; j < arr.length; j++) { // If for current inversion, // GCD of both elements is 1, // GCD of both the indices if (arr[i] > arr[j] && __gcd(arr[i], arr[j]) == 1) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // Recursive Call for the // remaining array res = (res | isPossible(arr)); // Backtrack temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } // Return Answer return res; } // Driver Code let arr = [1, 9, 3, 7, 2, 4]; if (isPossible(arr)) document.write("Possible") else document.write("Not Possible"); // This code is contributed by Potta Lokesh </script> |
Output
Possible
Time Complexity: O(N2N!)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
