GCD Sort of an Array

To solve this problem, we’ll use the Union-Find data structure to determine if it’s possible to sort the given array nums using the specified swapping conditions.

We’ll first create a set of primes that are less than the maximum value in nums. Then, we’ll use these primes to create groups of connected numbers using Union-Find, where two numbers are connected if they have a common factor greater than 1.

Finally, we’ll check if the original and sorted arrays are compatible, considering these connections.

Here’s a Python function that implements the algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from collections import defaultdict
from math import isqrt

class Solution:
    def gcdSort(self, nums: List[int]) -> bool:
        # Find all primes less than the maximum value in nums
        max_num = max(nums)
        is_prime = [True] * (max_num + 1)
        is_prime[0] = is_prime[1] = False
        primes = []
        for i in range(2, max_num + 1):
            if is_prime[i]:
                primes.append(i)
                for j in range(i * i, max_num + 1, i):
                    is_prime[j] = False

        # Union-Find functions
        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            parent[find(x)] = find(y)

        # Initialize Union-Find
        parent = list(range(max_num + 1))

        # Connect numbers that have common factors
        for num in nums:
            original_num = num
            for prime in primes:
                if prime > isqrt(original_num):
                    break
                if num % prime == 0:
                    union(original_num, prime)
                    while num % prime == 0:
                        num //= prime
            if num > 1:
                union(original_num, num)

        # Check if original and sorted arrays are compatible
        sorted_nums = sorted(nums)
        for num, sorted_num in zip(nums, sorted_nums):
            if find(num) != find(sorted_num):
                return False
        return True

The code first determines the prime numbers less than the maximum value in nums. Then, it uses Union-Find to group numbers that have common factors greater than 1. Finally, it checks whether the original array and the sorted array are compatible according to these groups. If any mismatch is found, the function returns False; otherwise, it returns True.