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
.