In this article, we have explored an insightful approach/ algorithm to sort an array by comparing the Greatest Common Divisor of two of the elements.

Reading time: 25 minutes | Coding time: 25 minutes

TABLE OF CONTENTS

• Pre-requisites
• Problem statement definition
• Intuition (Arriving at the solution)
• Optimization
• Algorithm
• Psuedocode
• Implementation
  • JAVA code
  • Python code
  • C++ code
• Time-complexity analysis
• Space-Complexity analysis

PRE-REQUISITES

• Eucledian Algorithm
• Greatest Common Divisor
• Factorization Algorithms
• Sieve
• Time-Complexity Analysis

This is a problem statement which is named '1998. GCD Sort of an Array' in Leetcode.

PROBLEM STATEMENT DEFINITION

This problem involves sorting an array by finding the gcd of two elements of an array!

Program Prompt

We are given an integer array (called nums) , and we can perform the following operation any number of times on nums:

Swap the positions of two elements nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j].

We also have to return true if it is possible to sort the array in ascending order using the above swap method, or false otherwise.

Constraints (as per the problem on Leetcode)

• 1 <= nums.length <= 3 * 10^4
• 2 <= nums[i] <= 10^5

Example-1:

Input: nums = [7,21,3]
Output: true
Explanation: We can sort [7,21,3] by performing the following operations:

• Swap 7 and 21 because gcd(7,21) = 7. nums = [21,7,3]
• Swap 21 and 3 because gcd(21,3) = 3. nums = [3,7,21]

Example-2:

Input: nums = [5,2,6,2]
Output: false
Explanation: It is impossible to sort the array because 5 cannot be swapped with any other element.

Example-3:

Input: nums = [10,5,9,3,15]
Output: true
We can sort [10,5,9,3,15] by performing the following operations:

• Swap 10 and 15 because gcd(10,15) = 5. nums = [15,5,9,3,10]
• Swap 15 and 3 because gcd(15,3) = 3. nums = [3,5,9,15,10]
• Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,10,15]

INTUITION (ARRIVING AT THE SOLUTION)

As per the problem statement, we can swap only those elements which have gcd>1. In other words, at least one common factor other than 1 because only than gcd will be greater than 1.
We can try a brute force approach - check for others element whether they have factors in common or not and trying out each permutation. But this approach exceeds the time limit as it works in exponential time complexity. So, we need to optimise it.

OPTIMIZATION

Since we need to sort it in non decreasing order (or ascending order ), we can compare the respective elements of sorted and unsorted array and check whether nums[i] can be swapped with sorted_nums[i] . Thus, we would save our time complexity of checking for permutation.

Efficient Swapping!

• Find out the factors by finding out the smallest prime factor using sieveand dividing the number of concern repetitively by its shortest_prime_factors. Thus, we get its factors. Then , we use the Disjoint set union data structure & make the union of number of concern and its factors.

• So, after making the union sets of all the elements, check whether the nums[i] and sorted_nums[i] belong to the same union set or not? If they belong to the same set, means that they have some factors in common, Thats why we can swap them. Hence we can use union find here.

• If they do not belong to the same set, i.e., there is no common factors between them, hence we cannot swap them , thus, sorted_nums can not be obtained. So, return false.

• Else if all the respective pairs of sorted_nums[i] and nums[i] can be swapped, then, we can obtain sorted order, hence ,return true.

ALGORITHM

• As per the idea discussed, we create a sorted version of nums, let say sorted_nums.
• Then we compare each element belong nums and sorted_nums, check if we can swap nums[i] to become sorted_nums[i].
• If we can't swap nums[i] to become sorted_nums[i] then return False
• Otherwise, if we can swap all pairs nums[i], sorted_nums[i] then return True.
• To check if we can swap(nums[i], sorted_nums[i]), we need Union-Find to group numbers the same factors together.
• Use sieve with time complexity O(N) to calculate smallest_prime_factor[x] array, where smallest_prime_factor[x] is the smallest prime factor of number x, where x >= 2.
• Then iterate each element num in nums:
• Get factors of num in O(logNum) since we use smallest_prime_factor[x].
• Union num and their factors together.

PSUEDOCODE

vector<int> par,rank;
    int n;
    public:
    DSU(int n)
    {
        this->par.resize(n);
        this->rank.resize(n);
        this->n=n;
        for(int i=0;i<n;i++)
            par[i]=i;
    }
    int find(int x)
    {
        if(x==par[x])return x;
        return par[x]=find(par[x]);
    }
    void Union(int a, int b)
    {
        int a_par=find(a);
        int b_par=find(b);
        if(a_par==b_par)
            return;
        if(rank[a_par]<rank[b_par])
        {
            par[a_par]=b_par;
        }
        else if(rank[b_par]<rank[a_par]){
            par[b_par]=a_par;
        }
        else
        {
            par[a_par]=b_par;
            rank[b_par]+=1;
        }
    }

vector<int>shortest_prime_factors;
    bool gcdSort(vector<int>& nums) {
        int n=nums.size();
        int max_nums=INT_MIN;
        for(int i=0;i<n;i++)
            max_nums=max(max_nums,nums[i]);
        sieve(max_nums+1);
        DSU dsu(max_nums+1);
        vector<int>sortedNums(nums);
        sort(sortedNums.begin(),sortedNums.end());
        for(int i=0;i<n;i++)
        {
            vector<int>factorsOfNumsi= getAllFactors(nums[i]);
            int numFactors=factorsOfNumsi.size();
            for(int j=0;j<numFactors;j++)
            {
                dsu.Union(nums[i],factorsOfNumsi[j]);
            }
        }
        for(int i=0;i<n;i++)
        {
            if(dsu.find(nums[i])!=dsu.find(sortedNums[i]))
                return false;
        }
        return true;
        
    }
    vector<int> getAllFactors(int x)
    {
        vector<int>factors;
        while(x>1)
        {
            factors.push_back(shortest_prime_factors[x]);
            x/=shortest_prime_factors[x];
        }
        return factors;
    }
    void sieve(int n)
    {
        shortest_prime_factors.resize(n);
        for(int i=2;i<n;i++)
            shortest_prime_factors[i]=i;
        for(int i=2;i*i<n;i++)
        {
            if(shortest_prime_factors[i]==i)
            {
                for(int j=i*i;j<n;j+=i)
                {
                    if(shortest_prime_factors[j]>i)
                        shortest_prime_factors[j]=i;
                }
            }
        }
    }
    

IMPLEMENTATION

1. JAVA code:

public boolean gcdSort(int[] nums) {
        int max = 0;
        int[] sorted_nums = new int[nums.length];
        int index = 0;
        for(int e: nums) {
            max = Math.max(max, e);
            sorted_nums[index++] = e;
        }
        
        Arrays.sort(sorted_nums);
        
        int[] parent = new int[max + 1];
        int[] rank = new int[max + 1];
        for(int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        int[] smallPrimeFactor = sieve(max + 1);
        
        for(int e: nums) {
            for(int p: getCurrentPrimeFactor(e, smallPrimeFactor)) {
                union(parent, rank, e, p);
            }
        }
        
        for(int i = 0; i< nums.length; i++) {
            if(find(parent, nums[i]) != find(parent, sorted_nums[i])) return false;
        }
        
        return true;
    }
    
    private int[] sieve(int n) {
        int[] minPrimeArray = new int[n];
        
        for(int i = 2; i < n; i++) {
            minPrimeArray[i] = i;
        }
        
        for(int i = 2; i * i < n; i++) {
            if(minPrimeArray[i] != i) continue;
            for(int j = i * i; j < n; j += i) {
                if (minPrimeArray[j] > i) minPrimeArray[j] = i;
            }
        }
        
        return minPrimeArray;
    }
    
    private List<Integer> getCurrentPrimeFactor(int n, int[] smallPrimeFactor) {
        List<Integer> list = new LinkedList<>();

        while(n > 1) {
            list.add(smallPrimeFactor[n]);
            n /= smallPrimeFactor[n];
        }
        
        return list;
    }
    
    private void union(int[] parent, int[] rank, int a, int b) {
        int parentA = find(parent, a);
        int parentB = find(parent, b);
        
        if(rank[parentA] > rank[parentB]) {
            parent[parentB] = parent[parentA];
        } else if(rank[parentA] < rank[parentB]) {
            parent[parentA] = parent[parentB];
        } else {
            parent[parentB] = parent[parentA];
            rank[parentA]++;
        }
    }
    
    private int find(int[] parent, int a) {
        if(a != parent[a]) {
            a = find(parent, parent[a]);
        }
        
        return parent[a];
    }

2. Python Code

class UnionFind:
    def __init__(self):
        self.parent = {}

    def find(self, u):
        if u != self.parent.setdefault(u, u):
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu != pv: self.parent[pu] = pv


class Solution:
    def gcdSort(self, nums: List[int]) -> bool:
        def sieve(n):  # O(N*log(logN)) ~ O(N)
            shortest_prime_factors = [i for i in range(n)]
            for i in range(2, n):
                if shortest_prime_factors[i] != i: continue  # Skip if it's a not prime number
                for j in range(i * i, n, i):
                    if shortest_prime_factors[j] > i:  # update to the smallest prime factor of j
                        shortest_prime_factors[j] = i
            return shortest_prime_factors

        def getPrimeFactors(num, shortest_prime_factors):  # O(logNum)
            while num > 1:
                yield shortest_prime_factors[num]
                num //= shortest_prime_factors[num]

        shortest_prime_factors = sieve(max(nums) + 1)
        uf = UnionFind()
        for x in nums:
            for f in getPrimeFactors(x, shortest_prime_factors):
                uf.union(x, f)

        for x, y in zip(nums, sorted(nums)):
            if uf.find(x) != uf.find(y):
                return False

        return True

3. C++ code

class UnionFind {
    vector<int> parent;
public:
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]); // Path compression
    }
    void Union(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu != pv) parent[pu] = pv;
    }
};
class Solution {
public:
    vector<int> shortest_prime_factors; 
    bool gcdSort(vector<int>& nums) {
        int maxNum = *max_element(nums.begin(), nums.end());
        sieve(maxNum + 1);

        UnionFind uf(maxNum+1);
        for (int x : nums)
            for (int f : getPrimeFactors(x))
                uf.Union(x, f);

        vector<int> sortedArr(nums);
        sort(sortedArr.begin(), sortedArr.end());
        for (int i = 0; i < nums.size(); ++i)
            if (uf.find(nums[i]) != uf.find(sortedArr[i]))
                return false; 
        return true;
    }
    void sieve(int n) { /
        shortest_prime_factors.resize(n);
        for (int i = 2; i < n; ++i) shortest_prime_factors[i] = i;
        for (int i = 2; i * i < n; i++) {
            if (shortest_prime_factors[i] != i) continue; 
            for (int j = i * i; j < n; j += i)
                if (shortest_prime_factors[j] > i) shortest_prime_factors[j] = i; of j
        }
    }
    vector<int> getPrimeFactors(int n) { 
        vector<int> factors;
        while (n > 1) {
            factors.push_back(shortest_prime_factors[n]);
            n /= shortest_prime_factors[n];
        }
        return factors;
    }
};

The codes discussed here pass all test cases!

TIME COMPLEXITY ANALYSIS:

• We take NlogN time to get the factors of all numbers (logN for one number).
• If the greatest integer in the array is max_num, then
• We take
  • O(max_num) to find the smallest_prime_factor
  • For the sieve the number of iterations depends on the max_num because that is the greatest gcd that is present in the array. Thus the time taken for sieve is O(max_num * log(log(max_num))
  • O(nlogn) for sorting.

Thus the time complexity is:

• Worst case time complexity: Θ(max_num + max_num * log(log(max_num)) + nlogn)
• Average case time complexity: Θ(max_num + max_num * log(log(max_num)) + nlogn)
• Best case time complexity: Θ(max_num + nlogn), if log(log(max_num)<<<1

SPACE COMPLEXITY ANALYSIS:

A common trade-off among all algorithms is the relation between the time-complexity and the auxiliary space used! The solution in this article also follows this same principle.

We use an extra space of 'n' size to store the sorted array. This enables us to have the input array unchanged during computation. We also have to have an array which acts as a sieve. Keeping in mind the constraints and the approach, we know that the largest gcd possible is max_num ( gcd(max_num, max_num) = max_num ). Thus we allocate an auxiliary space of max_num for the sieve.

Thus the overall Space complexity is Θ(max_num + n)

With this article at OpenGenus, you must have the complete idea of solving GCD Sort of an Array efficiently!