In this guide, you will get 1998. GCD Sort of an Array LeetCode Solution with the best time and space complexity. The solution to GCD Sort of an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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]
Time Complexity: O(k\log^* k + k\log(\log k) + \texttt{sort}(n)), where k = \max(\texttt{nums})
Space Complexity: O(\max(\texttt{nums}) + n)
1998. GCD Sort of an Array LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), rank(n) {
iota(id.begin(), id.end(), 0);
}
void unionByRank(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
private:
vector<int> id;
vector<int> rank;
};
class Solution {
public:
bool gcdSort(vector<int>& nums) {
const int mx = ranges::max(nums);
const vector<int> minPrimeFactors = sieveEratosthenes(mx + 1);
UnionFind uf(mx + 1);
for (const int num : nums)
for (const int primeFactor : getPrimeFactors(num, minPrimeFactors))
uf.unionByRank(num, primeFactor);
vector<int> sortedNums(nums);
ranges::sort(sortedNums);
for (int i = 0; i < nums.size(); ++i)
// Can't swap nums[i] with sortedNums[i].
if (uf.find(nums[i]) != uf.find(sortedNums[i]))
return false;
return true;
}
private:
// Gets the minimum prime factor of i, where 1 < i <= n.
vector<int> sieveEratosthenes(int n) {
vector<int> minPrimeFactors(n + 1);
iota(minPrimeFactors.begin() + 2, minPrimeFactors.end(), 2);
for (int i = 2; i * i < n; ++i)
if (minPrimeFactors[i] == i) // `i` is prime.
for (int j = i * i; j < n; j += i)
minPrimeFactors[j] = min(minPrimeFactors[j], i);
return minPrimeFactors;
}
vector<int> getPrimeFactors(int num, const vector<int>& minPrimeFactors) {
vector<int> primeFactors;
while (num > 1) {
const int divisor = minPrimeFactors[num];
primeFactors.push_back(divisor);
while (num % divisor == 0)
num /= divisor;
}
return primeFactors;
}
}; /* code provided by PROGIEZ */
1998. GCD Sort of an Array LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public void unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
private int[] id;
private int[] rank;
}
class Solution {
public boolean gcdSort(int[] nums) {
final int mx = Arrays.stream(nums).max().getAsInt();
final int[] minPrimeFactors = sieveEratosthenes(mx + 1);
UnionFind uf = new UnionFind(mx + 1);
for (final int num : nums)
for (final int primeFactor : getPrimeFactors(num, minPrimeFactors))
uf.unionByRank(num, primeFactor);
int[] sortedNums = nums.clone();
Arrays.sort(sortedNums);
for (int i = 0; i < nums.length; ++i)
// Can't swap nums[i] with sortedNums[i].
if (uf.find(nums[i]) != uf.find(sortedNums[i]))
return false;
return true;
}
// Gets the minimum prime factor of i, where 1 < i <= n.
private int[] sieveEratosthenes(int n) {
int[] minPrimeFactors = new int[n + 1];
for (int i = 2; i <= n; ++i)
minPrimeFactors[i] = i;
for (int i = 2; i * i < n; ++i)
if (minPrimeFactors[i] == i) // `i` is prime.
for (int j = i * i; j < n; j += i)
minPrimeFactors[j] = Math.min(minPrimeFactors[j], i);
return minPrimeFactors;
}
private List<Integer> getPrimeFactors(int num, int[] minPrimeFactors) {
List<Integer> primeFactors = new ArrayList<>();
while (num > 1) {
final int divisor = minPrimeFactors[num];
primeFactors.add(divisor);
while (num % divisor == 0)
num /= divisor;
}
return primeFactors;
}
} // code provided by PROGIEZ
1998. GCD Sort of an Array LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
def unionByRank(self, u: int, v: int) -> None:
i = self.find(u)
j = self.find(v)
if i == j:
return False
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
return True
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
class Solution:
def gcdSort(self, nums: list[int]) -> bool:
mx = max(nums)
minPrimeFactors = self._sieveEratosthenes(mx + 1)
uf = UnionFind(mx + 1)
for num in nums:
for primeFactor in self._getPrimeFactors(num, minPrimeFactors):
uf.unionByRank(num, primeFactor)
for a, b in zip(nums, sorted(nums)):
# Can't swap nums[i] with sortedNums[i].
if uf.find(a) != uf.find(b):
return False
return True
def _sieveEratosthenes(self, n: int) -> list[int]:
"""Gets the minimum prime factor of i, where 1 < i <= n."""
minPrimeFactors = [i for i in range(n + 1)]
for i in range(2, int(n**0.5) + 1):
if minPrimeFactors[i] == i: # `i` is prime.
for j in range(i * i, n, i):
minPrimeFactors[j] = min(minPrimeFactors[j], i)
return minPrimeFactors
def _getPrimeFactors(self, num: int, minPrimeFactors: list[int]) -> list[int]:
primeFactors = []
while num > 1:
divisor = minPrimeFactors[num]
primeFactors.append(divisor)
while num % divisor == 0:
num //= divisor
return primeFactors # code by PROGIEZ
