Formatted question description: https://leetcode.ca/all/1998.html
1998. GCD Sort of an Array
Level
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]
andnums[j]
ifgcd(nums[i], nums[j]) > 1
wheregcd(nums[i], nums[j])
is the greatest common divisor ofnums[i]
andnums[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);
}
}