2709. Greatest Common Divisor Traversal LeetCode Solution
In this guide, you will get 2709. Greatest Common Divisor Traversal LeetCode Solution with the best time and space complexity. The solution to Greatest Common Divisor Traversal 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.
Problem Statement of Greatest Common Divisor Traversal
You are given a 0-indexed integer array nums, and you are allowed to traverse between its indices. You can traverse between index i and index j, i != j, if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.
Your task is to determine if for every pair of indices i and j in nums, where i < j, there exists a sequence of traversals that can take us from i to j.
Return true if it is possible to traverse between all such pairs of indices, or false otherwise.
Example 1:
Input: nums = [2,3,6]
Output: true
Explanation: In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2).
To go from index 0 to index 1, we can use the sequence of traversals 0 -> 2 -> 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1.
To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1.
Input: nums = [3,9,5]
Output: false
Explanation: No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.
Example 3:
Input: nums = [4,3,12,8]
Output: true
Explanation: There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
Complexity Analysis
Time Complexity: O(k\log^* k + k\log(\log k), where k = \max(\texttt{nums})
Space Complexity: O(n)
2709. Greatest Common Divisor Traversal LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), sz(n, 1) {
iota(id.begin(), id.end(), 0);
}
void unionBySize(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (sz[i] < sz[j]) {
sz[j] += sz[i];
id[i] = j;
} else {
sz[i] += sz[j];
id[j] = i;
}
}
int getSize(int i) {
return sz[i];
}
private:
vector<int> id;
vector<int> sz;
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
};
class Solution {
public:
bool canTraverseAllPairs(vector<int>& nums) {
const int n = nums.size();
const int mx = ranges::max(nums);
const vector<int> minPrimeFactors = sieveEratosthenes(mx + 1);
unordered_map<int, int> primeToFirstIndex;
UnionFind uf(n);
for (int i = 0; i < n; ++i)
for (const int primeFactor : getPrimeFactors(nums[i], minPrimeFactors))
// `primeFactor` already appeared in the previous indices.
if (const auto it = primeToFirstIndex.find(primeFactor);
it != primeToFirstIndex.cend())
uf.unionBySize(it->second, i);
else
primeToFirstIndex[primeFactor] = i;
for (int i = 0; i < n; ++i)
if (uf.getSize(i) == n)
return true;
return false;
}
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 */
2709. Greatest Common Divisor Traversal LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
sz = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
for (int i = 0; i < n; ++i)
sz[i] = 1;
}
public void unionBySize(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (sz[i] < sz[j]) {
sz[j] += sz[i];
id[i] = j;
} else {
sz[i] += sz[j];
id[j] = i;
}
}
public int getSize(int i) {
return sz[i];
}
private int[] id;
private int[] sz;
private int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}
class Solution {
public boolean canTraverseAllPairs(int[] nums) {
final int n = nums.length;
final int mx = Arrays.stream(nums).max().getAsInt();
final int[] minPrimeFactors = sieveEratosthenes(mx + 1);
Map<Integer, Integer> primeToFirstIndex = new HashMap<>();
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; ++i)
for (final int primeFactor : getPrimeFactors(nums[i], minPrimeFactors))
// `primeFactor` already appeared in the previous indices.
if (primeToFirstIndex.containsKey(primeFactor))
uf.unionBySize(primeToFirstIndex.get(primeFactor), i);
else
primeToFirstIndex.put(primeFactor, i);
for (int i = 0; i < n; ++i)
if (uf.getSize(i) == n)
return true;
return false;
}
// 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
2709. Greatest Common Divisor Traversal LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.sz = [1] * n
def unionBySize(self, u: int, v: int) -> None:
i = self._find(u)
j = self._find(v)
if i == j:
return
if self.sz[i] < self.sz[j]:
self.sz[j] += self.sz[i]
self.id[i] = j
else:
self.sz[i] += self.sz[j]
self.id[j] = i
def getSize(self, i: int) -> int:
return self.sz[i]
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 canTraverseAllPairs(self, nums: list[int]) -> bool:
n = len(nums)
mx = max(nums)
maxPrimeFactor = self._sieveEratosthenes(mx + 1)
primeToFirstIndex = collections.defaultdict(int)
uf = UnionFind(n)
for i, num in enumerate(nums):
for prime_factor in self._getPrimeFactors(num, maxPrimeFactor):
if prime_factor in primeToFirstIndex:
uf.unionBySize(primeToFirstIndex[prime_factor], i)
else:
primeToFirstIndex[prime_factor] = i
return any(uf.getSize(i) == n for i in range(n))
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
