Problem Statement
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.
Example 2
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.
Try here before watching the video.
Video Solution
Java Code
class UnionFind {
private int[] rank;
private int[] parent;
public UnionFind(int n) {
this.parent = new int[n];
this.rank = new int[n];
for(int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if(parent[x] != x) {
parent[x] = find(parent[x]); // doing path compression
}
return parent[x];
}
public void union(int x, int y) {
int parentX = find(x);
int parentY = find(y);
if(parentX != parentY) {
if(rank[parentX] > rank[parentY]) {
parent[parentY] = parentX;
rank[parentX] += rank[parentY];
} else {
parent[parentX] = parentY;
rank[parentY] += rank[parentX];
}
}
}
}
class Solution {
public boolean canTraverseAllPairs(int[] nums) {
int MAX = 100000;
int N = nums.length;
boolean[] has = new boolean[MAX + 1];
for (int x : nums) {
has[x] = true;
}
// edge cases
if (N == 1) {
return true;
}
if (has[1]) {
return false;
}
// the general solution
int[] sieve = new int[MAX + 1];
for (int d = 2; d <= MAX; d++) {
if (sieve[d] == 0) {
for (int v = d; v <= MAX; v += d) {
sieve[v] = d;
}
}
}
UnionFind union = new UnionFind(2 * MAX + 1);
for (int x : nums) {
int val = x;
while (val > 1) {
int prime = sieve[val];
int root = prime+MAX;
if (union.find(root) != union.find(x)) {
union.union(root, x);
}
while (val % prime == 0) {
val /= prime;
}
}
}
int cnt = 0;
for (int i = 2; i <= MAX; i++) {
if (has[i] && union.find(i) == i) {
cnt++;
}
}
return cnt == 1;
}
}
C++ Code
class UnionFind {
private:
vector<int> rank;
vector<int> parent;
public:
UnionFind(int n) {
parent.resize(n);
rank.resize(n);
for(int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if(parent[x] != x) {
parent[x] = find(parent[x]); // doing path compression
}
return parent[x];
}
void union_(int x, int y) {
int parentX = find(x);
int parentY = find(y);
if(parentX != parentY) {
if(rank[parentX] > rank[parentY]) {
parent[parentY] = parentX;
rank[parentX] += rank[parentY];
} else {
parent[parentX] = parentY;
rank[parentY] += rank[parentX];
}
}
}
};
class Solution {
public:
bool canTraverseAllPairs(vector<int>& nums) {
int MAX = 100000;
int N = nums.size();
vector<bool> has(MAX + 1, false);
for (int x : nums) {
has[x] = true;
}
// edge cases
if (N == 1) {
return true;
}
if (has[1]) {
return false;
}
// the general solution
vector<int> sieve(MAX + 1, 0);
for (int d = 2; d <= MAX; d++) {
if (sieve[d] == 0) {
for (int v = d; v <= MAX; v += d) {
sieve[v] = d;
}
}
}
UnionFind union_(2 * MAX + 1);
for (int x : nums) {
int val = x;
while (val > 1) {
int prime = sieve[val];
int root = prime+MAX;
if (union_.find(root) != union_.find(x)) {
union_.union_(root, x);
}
while (val % prime == 0) {
val /= prime;
}
}
}
int cnt = 0;
for (int i = 2; i <= MAX; i++) {
if (has[i] && union_.find(i) == i) {
cnt++;
}
}
return cnt == 1;
}
};
Python Code
This code might give TLE, but if you will run the same code on those test cases. It will work fine. I was trying to figure out why is it happening. But due to time constraints, I couldn't spend much time. If you come to know why is it happening. Please let us know on our Discord Server.
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # doing path compression
return self.parent[x]
def union(self, x, y):
parentX = self.find(x)
parentY = self.find(y)
if parentX != parentY:
if self.rank[parentX] > self.rank[parentY]:
self.parent[parentY] = parentX
self.rank[parentX] += self.rank[parentY]
else:
self.parent[parentX] = parentY
self.rank[parentY] += self.rank[parentX]
class Solution:
def canTraverseAllPairs(self, nums):
MAX = 100000
N = len(nums)
has = [False] * (MAX + 1)
for x in nums:
has[x] = True
# edge cases
if N == 1:
return True
if has[1]:
return False
# the general solution
sieve = [0] * (MAX + 1)
for d in range(2, MAX + 1):
if sieve[d] == 0:
for v in range(d, MAX + 1, d):
sieve[v] = d
union = UnionFind(2 * MAX + 1)
for x in nums:
val = x
while val > 1:
prime = sieve[val]
root = prime + MAX
if union.find(root) != union.find(x):
union.union(root, x)
while val % prime == 0:
val //= prime
cnt = 0
for i in range(2, MAX + 1):
if has[i] and union.find(i) == i:
cnt += 1
return cnt == 1
Javascript Code
This code might give TLE, but if you will run the same code on those test cases. It will work fine. I was trying to figure out why is it happening. But due to time constraints, I couldn't spend much time. If you come to know why is it happening. Please let us know on our Discord Server.
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // doing path compression
}
return this.parent[x];
}
union(x, y) {
const parentX = this.find(x);
const parentY = this.find(y);
if (parentX !== parentY) {
if (this.rank[parentX] > this.rank[parentY]) {
this.parent[parentY] = parentX;
this.rank[parentX] += this.rank[parentY];
} else {
this.parent[parentX] = parentY;
this.rank[parentY] += this.rank[parentX];
}
}
}
}
var canTraverseAllPairs = function(nums) {
const MAX = 100000;
const N = nums.length;
const has = Array(MAX + 1).fill(false);
for (const x of nums) {
has[x] = true;
}
// edge cases
if (N === 1) {
return true;
}
if (has[1]) {
return false;
}
// the general solution
const sieve = Array(MAX + 1).fill(0);
for (let d = 2; d <= MAX; d++) {
if (sieve[d] === 0) {
for (let v = d; v <= MAX; v += d) {
sieve[v] = d;
}
}
}
const union = new UnionFind(2 * MAX + 1);
for (const x of nums) {
let val = x;
while (val > 1) {
const prime = sieve[val];
const root = prime + MAX;
if (union.find(root) !== union.find(x)) {
union.union(root, x);
}
while (val % prime === 0) {
val /= prime;
}
}
}
let cnt = 0;
for (let i = 2; i <= MAX; i++) {
if (has[i] && union.find(i) === i) {
cnt++;
}
}
return cnt === 1;
};
Go Code
type UnionFind struct {
parent []int
rank []int
}
func NewUnionFind(n int) *UnionFind {
parent := make([]int, n)
rank := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
}
return &UnionFind{parent, rank}
}
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x]) // doing path compression
}
return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) {
parentX := uf.Find(x)
parentY := uf.Find(y)
if parentX != parentY {
if uf.rank[parentX] > uf.rank[parentY] {
uf.parent[parentY] = parentX
uf.rank[parentX] += uf.rank[parentY]
} else {
uf.parent[parentX] = parentY
uf.rank[parentY] += uf.rank[parentX]
}
}
}
func canTraverseAllPairs(nums []int) bool {
MAX := 100000
N := len(nums)
has := make([]bool, MAX+1)
for _, x := range nums {
has[x] = true
}
// edge cases
if N == 1 {
return true
}
if has[1] {
return false
}
// the general solution
sieve := make([]int, MAX+1)
for d := 2; d <= MAX; d++ {
if sieve[d] == 0 {
for v := d; v <= MAX; v += d {
sieve[v] = d
}
}
}
union := NewUnionFind(2*MAX + 1)
for _, x := range nums {
val := x
for val > 1 {
prime := sieve[val]
root := prime + MAX
if union.Find(root) != union.Find(x) {
union.Union(root, x)
}
for val%prime == 0 {
val /= prime
}
}
}
cnt := 0
for i := 2; i <= MAX; i++ {
if has[i] && union.Find(i) == i {
cnt++
}
}
return cnt == 1
}
Complexity Analysis
There are less than MAX_VAL additional dummy nodes, and because any integer at most MAX_VAL will have at most 6 distinct prime factors, the graph will have at most 6n edges. To iterate over all prime factors efficiently, we can consider the harmonic series, or use the sieve of the Eratosthenes algorithm to build this graph in O(n log(MAX_VAL)) with O(n) memory. Checking the connectivity of this graph can be done with either BFS/DFS or union find, which can be done in O(n).
- Time Complexity: O(n * log(MAX_VAL))
- Space Complexity: O(n)
The time complexity of union-find (DSU) can be treated as O(n) only when both path-compression and rank-by-size are applied, which is used in the above solution code.