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] 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);
        }
    }
    
  • // 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;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions