# GCD Sort of an Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/gcd-sort-of-an-array)
Canonical: https://scaleengineer.com/dsa/problems/gcd-sort-of-an-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array
---
## Problem
You are given an integer array `nums`, and you 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]`.

Return `true` _if it is possible to sort_ `nums` _in **non-decreasing** order using the above swap method, or_ `false` _otherwise._

**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**]

**Constraints:**

* `1 <= nums.length <= 3 * 104`
* `2 <= nums[i] <= 105`

# Approaches
## Pairwise GCD with Union-Find
This approach models the problem as finding connected components. Two numbers can be swapped if their GCD is greater than 1. This transitive relationship means all numbers that can be swapped with each other form a single group or component. We can use a Union-Find data structure to efficiently manage these groups. The core idea is to iterate through all pairs of numbers in the input array. If their GCD is greater than 1, we union them into the same set. After processing all pairs, we check if each number in the original array belongs to the same set as the number that should be in its position in the sorted version of the array.
**Time:** O(U^2 * log(M) + N log N), where `N` is the length of `nums`, `U` is the number of unique elements, and `M` is the maximum value. The `U^2` term for checking all pairs makes this too slow for the given constraints. · **Space:** O(M + N), where `M` is the maximum value in `nums` and `N` is the length of `nums`. This is for the DSU structure (if using an array up to `M`) and the sorted copy of the array.
**Pros:** Conceptually simpler than the prime factorization approach.; Directly models the swap condition of the problem.
**Cons:** Inefficient due to the quadratic complexity of checking all pairs of numbers, leading to a "Time Limit Exceeded" error on large inputs.
### Explanation
This approach is a direct translation of the problem's swap condition into a connectivity problem. We treat each unique number as a node in a graph and an edge exists between two nodes if their GCD is greater than 1. Instead of building an explicit graph, we use a Union-Find data structure to maintain the connected components (sets). We iterate through all possible pairs of unique numbers from the input array. For each pair, we compute their greatest common divisor (GCD). If the GCD is greater than 1, it means they can be swapped, so we merge their sets using the `union` operation. After checking all pairs, the Union-Find structure correctly represents all groups of inter-swappable numbers. The final step is to verify if the array is sortable. An array is sortable if and only if for every position `i`, the original number `nums[i]` can be moved to the position of `sortedNums[i]`, which is only possible if they belong to the same connected component. We check this by comparing the roots of `nums[i]` and `sortedNums[i]` in our DSU structure. If this holds for all `i`, the array is sortable.

```java
// DSU class implementation would be needed here.
// This is a conceptual example and will Time Out on larger test cases.
class Solution {
    public boolean gcdSort(int[] nums) {
        int n = nums.length;
        int[] sortedNums = nums.clone();
        Arrays.sort(sortedNums);

        int maxVal = 0;
        Set<Integer> uniqueNumsSet = new HashSet<>();
        for (int num : nums) {
            uniqueNumsSet.add(num);
            maxVal = Math.max(maxVal, num);
        }
        List<Integer> uniqueNums = new ArrayList<>(uniqueNumsSet);
        
        DSU dsu = new DSU(maxVal + 1);

        for (int i = 0; i < uniqueNums.size(); i++) {
            for (int j = i + 1; j < uniqueNums.size(); j++) {
                int u = uniqueNums.get(i);
                int v = uniqueNums.get(j);
                if (gcd(u, v) > 1) {
                    dsu.union(u, v);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (dsu.find(nums[i]) != dsu.find(sortedNums[i])) {
                return false;
            }
        }
        return true;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- Create a sorted copy of the input array `nums`, let's call it `sortedNums`.
- Find the set of unique numbers present in `nums`.
- Initialize a Union-Find (Disjoint Set Union) data structure. A map can be used to store the parent of each unique number, or an array if the numbers are within a reasonable range.
- Iterate through every pair of unique numbers `(u, v)`.
- Calculate `gcd(u, v)`. If it's greater than 1, perform a `union(u, v)` operation to group them in the same set.
- After building the sets, iterate from `i = 0` to `n-1`.
- For each index `i`, check if `nums[i]` and `sortedNums[i]` are in the same set by comparing their roots: `find(nums[i]) == find(sortedNums[i])`.
- If they are not in the same set for any `i`, it's impossible to sort the array, so return `false`.
- If the loop completes without returning, it means every element can be moved to its sorted position. Return `true`.

## Union-Find with Prime Factorization
This is an optimized approach that avoids the quadratic complexity of checking all pairs. The core insight is that two numbers can be swapped if and only if they share a common prime factor. Instead of connecting numbers directly, we connect each number to its prime factors. If two numbers share a prime factor, they will be transitively connected through that prime factor and end up in the same set. This significantly reduces the number of union operations needed, leading to a much more efficient solution.
**Time:** O(N*log(N) + M*log(log(M)) + N*log(M)), where `N` is the length of `nums` and `M` is the maximum value. The main components are `O(M*log(log(M)))` for the Sieve, `O(N*log(M))` for prime factorization and union operations, and `O(N*log(N))` for sorting. This is efficient enough for the given constraints. · **Space:** O(N + M), where `N` is the length of `nums` and `M` is the maximum value. This space is used for the DSU structure, the SPF array, and the sorted copy of `nums`.
**Pros:** Highly efficient and passes the time limits for the given constraints.; Correctly and efficiently models the transitive nature of the swaps through common prime factors.
**Cons:** More complex to implement due to the need for a sieve and prime factorization logic.
### Explanation
The algorithm first determines the maximum number `maxVal` in the input array `nums`. A Union-Find (DSU) data structure is initialized to handle all integers from 2 up to `maxVal`. To efficiently find prime factors, we pre-compute the Smallest Prime Factor (SPF) for every number up to `maxVal` using a sieve-like method, which takes `O(M log log M)` time. Then, we iterate through each number `x` in the `nums` array. For each `x`, we find its prime factors using the pre-computed SPF array. The process of finding all prime factors for a number `k` is efficient, taking `O(log k)` time. For every prime factor `p` of `x`, we perform a `union(x, p)` operation. This links the number `x` to all its prime factors in the DSU structure. Consequently, any two numbers that share a prime factor will be placed in the same set. After processing all numbers and building the disjoint sets, we create a sorted copy of `nums`, called `sortedNums`. Finally, we iterate through the original array and the sorted array simultaneously. For each index `i`, we check if `nums[i]` and `sortedNums[i]` belong to the same set using `find(nums[i]) == find(sortedNums[i])`. If this condition fails for any index, it means `nums[i]` cannot be moved to its correct sorted position, and we return `false`. If the loop completes, we return `true`.

```java
class DSU {
    private int[] parent;
    public DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }
    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
        }
    }
}

class Solution {
    public boolean gcdSort(int[] nums) {
        int n = nums.length;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        DSU dsu = new DSU(maxVal + 1);

        int[] spf = new int[maxVal + 1];
        for (int i = 2; i <= maxVal; i++) {
            spf[i] = i;
        }
        for (int i = 2; i * i <= maxVal; i++) {
            if (spf[i] == i) { // i is prime
                for (int j = i * i; j <= maxVal; j += i) {
                    if (spf[j] == j) { // if j's smallest prime factor is not set yet
                        spf[j] = i;
                    }
                }
            }
        }

        for (int num : nums) {
            int temp = num;
            while (temp > 1) {
                int p = spf[temp];
                dsu.union(num, p);
                while (temp % p == 0) {
                    temp /= p;
                }
            }
        }

        int[] sortedNums = nums.clone();
        Arrays.sort(sortedNums);

        for (int i = 0; i < n; i++) {
            if (dsu.find(nums[i]) != dsu.find(sortedNums[i])) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Find `maxVal`, the maximum element in `nums`.
- Initialize a DSU (Union-Find) data structure of size `maxVal + 1`.
- Pre-compute the Smallest Prime Factor (SPF) for all numbers up to `maxVal` using a sieve. This allows for fast prime factorization.
- For each number `x` in `nums`:
  - Find all unique prime factors `p` of `x`.
  - For each prime factor `p`, call `dsu.union(x, p)`. This connects `x` with all its prime factors.
- Create `sortedNums`, a sorted version of `nums`.
- For `i` from `0` to `nums.length - 1`:
  - If `dsu.find(nums[i]) != dsu.find(sortedNums[i])`, it means `nums[i]` cannot be moved to its correct sorted position. Return `false`.
- If the loop completes, return `true`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  boolean gcdSort(int[] nums) {
    int n = 100010;
    p = new int[n];
    Map<Integer, List<Integer>> f = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    int mx = 0;
    for (int num : nums) {
      mx = Math.max(mx, num);
    }
    for (int i = 2; i <= mx; ++i) {
      if (f.containsKey(i)) {
        continue;
      }
      for (int j = i; j <= mx; j += i) {
        f.computeIfAbsent(j, k->new ArrayList<>()).add(i);
      }
    }
    for (int i : nums) {
      for (int j : f.get(i)) {
        p[find(i)] = find(j);
      }
    }
    int[] s = new int[nums.length];
    System.arraycopy(nums, 0, s, 0, nums.length);
    Arrays.sort(s);
    for (int i = 0; i < nums.length; ++i) {
      if (s[i] != nums[i] && find(nums[i]) != find(s[i])) {
        return false;
      }
    }
    return true;
  }
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### Python

```python
class Solution:
    def gcdSort(self, nums: List[int]) -> bool: n = 10 ** 5 + 10 p = list(range(n)) f = defaultdict(list) mx = max(nums) for i in range(2, mx + 1): if f[i]: continue for j in range(i, mx + 1, i): f[j]. append(i) def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] for i in nums: for j in f[i]: p[find(i)] = find(j) s = sorted(nums) for i, num in enumerate(nums): if s[i] != num and find(num) != find(s[i]): return False return True

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  bool gcdSort(vector<int> &nums) {
    int n = 100010;
    p.resize(n);
    for (int i = 0; i < n; ++i)
      p[i] = i;
    int mx = 0;
    for (auto num : nums)
      mx = max(mx, num);
    unordered_map<int, vector<int>> f;
    for (int i = 2; i <= mx; ++i) {
      if (!f[i].empty())
        continue;
      for (int j = i; j <= mx; j += i)
        f[j].push_back(i);
    }
    for (int i : nums) {
      for (int j : f[i])
        p[find(i)] = find(j);
    }
    vector<int> s = nums;
    sort(s.begin(), s.end());
    for (int i = 0; i < nums.size(); ++i) {
      if (s[i] != nums[i] && find(s[i]) != find(nums[i]))
        return false;
    }
    return true;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```