##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1998.html

# 1998. GCD Sort of an Array

Hard

## Description

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

Explanation: 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 * 10^4
• 2 <= nums[i] <= 10^5

## Solution

Use union find to partition the numbers from 1 to 100000 into groups such that for any group, if a is in the group, then there always exists a number b such that gcd(a, b) > 1. Then generate a sorted version of nums, which is sorted. If for any 0 <= i < nums.length, nums[i] and sorted[i] belong to the same group, then return true. Otherwise, return false.

• class Solution {
public boolean gcdSort(int[] nums) {
int maxNum = 100000;
int[] parent = new int[maxNum + 1];
boolean[] exists = new boolean[maxNum + 1];
int length = nums.length;
for (int i = 0; i < length; i++)
exists[nums[i]] = true;
for (int i = 1; i <= maxNum; i++)
parent[i] = i;
for (int i = 1; i <= maxNum; i++) {
if (exists[i])
divide(parent, i);
}
int[] sorted = new int[length];
System.arraycopy(nums, 0, sorted, 0, length);
Arrays.sort(sorted);
for (int i = 0; i < length; i++) {
if (find(parent, sorted[i]) != find(parent, nums[i]))
return false;
}
return true;
}

public void union(int[] parent, int index1, int index2) {
parent[find(parent, index1)] = find(parent, index2);
}

public int find(int[] parent, int index) {
if (parent[index] != index)
parent[index] = find(parent, parent[index]);
return parent[index];
}

public int gcd(int num1, int num2) {
while (num2 != 0) {
int temp = num1;
num1 = num2;
num2 = temp % num2;
}
return num1;
}

public void divide(int[] parent, int x) {
int y = x;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
while (x % i == 0) {
x /= i;
union(parent, y, i);
}
}
}
if (x != 1)
union(parent, y, x);
}
}

############

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) {
}
}
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];
}
}

• // OJ: https://leetcode.com/problems/gcd-sort-of-an-array/
// Time: O(N * sqrt(M) + NlogN)
// Space: O(N * sqrt(M))
class UnionFind {
vector<int> id;
public:
UnionFind(int N) : id(N) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
id[find(a)] = find(b);
}
};
class Solution {
vector<int> factors(int n) {
vector<int> ans;
for (int d = 2; d * d <= n; ++d) {
if (n % d) continue;
ans.push_back(d);
while (n % d == 0) n /= d;
}
if (n > 1) ans.push_back(n);
return ans;
}
public:
bool gcdSort(vector<int>& A) {
unordered_map<int, int> m; // prime factor -> representative index
int N = A.size();
UnionFind uf(N);
for (int i = 0; i < N; ++i) {
for (int f : factors(A[i])) {
if (m.count(f)) uf.connect(m[f], i);
else m[f] = i;
}
}
unordered_map<int, vector<int>> groups;
for (int i = 0; i < N; ++i) {
groups[uf.find(i)].push_back(i);
}
vector<int> sorted(N);
for (auto &[_, before] : groups) {
auto after = before;
sort(begin(after), end(after), [&](int a, int b) { return A[a] < A[b]; });
for (int i = 0; i < before.size(); ++i) {
sorted[before[i]] = A[after[i]];
}
}
for (int i = 1; i < N; ++i) {
if (sorted[i] < sorted[i - 1]) return false;
}
return true;
}
};

• 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


• var p []int

func gcdSort(nums []int) bool {
n := 100010
p = make([]int, n)
for i := 0; i < n; i++ {
p[i] = i
}
mx := 0
for _, num := range nums {
mx = max(mx, num)
}
f := make([][]int, mx+1)
for i := 2; i <= mx; i++ {
if len(f[i]) > 0 {
continue
}
for j := i; j <= mx; j += i {
f[j] = append(f[j], i)
}
}
for _, i := range nums {
for _, j := range f[i] {
p[find(i)] = find(j)
}
}
s := make([]int, len(nums))
for i, num := range nums {
s[i] = num
}
sort.Ints(s)
for i, num := range nums {
if s[i] != num && find(s[i]) != find(num) {
return false
}
}
return true
}

func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}

func max(a, b int) int {
if a > b {
return a
}
return b
}