1998. GCD Sort of an Array

1998. GCD Sort of an Array (Hard)

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
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 * 104
• 2 <= nums[i] <= 105

Similar Questions:

• Rank Transform of a Matrix (Hard)

Solution 1. Factorization + Sort within Union

Assume A has N elements and the maximum number is M.

1. Factorize each A[i] and use UnionFind to connect numbers that share the same factors.
2. For the numbers in the same union, sort them inplace.
3. Check if the result array after sorting is non-decreasing.

• Step 1 takes O(N * sqrt(M)) time and O(N * sqrt(M)) space.
• Step 2 takes O(NlogN) time and O(N) space
• Step 3 takes O(N) time and O(1) space.

So, overall this solution takes O(N * sqrt(M) + NlogN) time and O(N * sqrt(M)) space.

// OJ: https://leetcode.com/problems/gcd-sort-of-an-array/
// Author: github.com/lzl124631x
// 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;
    }
};