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
class Solution {
public boolean gcdSort(int[] nums) {
for(int x: nums) {
int y = x;
for(int p=2; UF[y]==0 && p*p<=y; ++p) {
if (y % p == 0) {
union(x, p);
while(y % p == 0) y /= p;
}
}
if (y!=1) union(x, y);
}
int[] copy = nums.clone();
Arrays.sort(copy);
for(int i=0; i<nums.length; i++) {
if (find(nums[i])!=find(copy[i])) return false;
}
return true;
}
private int[] UF = new int[100001];
private int find(int x) {
if (UF[x]==0) return UF[x]=x;
return UF[x]==x? x: (UF[x]=find(UF[x]));
}
private void union(int x, int y) {
UF[find(x)] = UF[find(y)];
}
}
