Welcome to Subscribe On Youtube
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]) > 1wheregcd(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^42 <= 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) { 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]; } } -
// 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 }