Union Find
Array
Math
Number Theory
Description
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.
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
Solutions
Solution 1
Python3 Java C++ Go
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 class UnionFind :
def __init__ ( self , n ):
self . p = list ( range ( n ))
self . size = [ 1 ] * n
def find ( self , x ):
if self . p [ x ] != x :
self . p [ x ] = self . find ( self . p [ x ])
return self . p [ x ]
def union ( self , a , b ):
pa , pb = self . find ( a ), self . find ( b )
if pa == pb :
return False
if self . size [ pa ] > self . size [ pb ]:
self . p [ pb ] = pa
self . size [ pa ] += self . size [ pb ]
else :
self . p [ pa ] = pb
self . size [ pb ] += self . size [ pa ]
return True
mx = 100010
p = defaultdict ( list )
for x in range ( 1 , mx + 1 ):
v = x
i = 2
while i <= v // i :
if v % i == 0 :
p [ x ] . append ( i )
while v % i == 0 :
v //= i
i += 1
if v > 1 :
p [ x ] . append ( v )
class Solution :
def canTraverseAllPairs ( self , nums : List [ int ]) -> bool :
n = len ( nums )
m = max ( nums )
uf = UnionFind ( n + m + 1 )
for i , x in enumerate ( nums ):
for j in p [ x ]:
uf . union ( i , j + n )
return len ( set ( uf . find ( i ) for i in range ( n ))) == 1
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76 class UnionFind {
private int [] p ;
private int [] size ;
public UnionFind ( int n ) {
p = new int [ n ] ;
size = new int [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
p [ i ] = i ;
size [ i ] = 1 ;
}
}
public int find ( int x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ] );
}
return p [ x ] ;
}
public boolean union ( int a , int b ) {
int pa = find ( a ), pb = find ( b );
if ( pa == pb ) {
return false ;
}
if ( size [ pa ] > size [ pb ] ) {
p [ pb ] = pa ;
size [ pa ] += size [ pb ] ;
} else {
p [ pa ] = pb ;
size [ pb ] += size [ pa ] ;
}
return true ;
}
}
class Solution {
private static final int MX = 100010 ;
private static final List < Integer >[] P = new List [ MX ] ;
static {
Arrays . setAll ( P , k -> new ArrayList <> ());
for ( int x = 1 ; x < MX ; ++ x ) {
int v = x ;
int i = 2 ;
while ( i <= v / i ) {
if ( v % i == 0 ) {
P [ x ] . add ( i );
while ( v % i == 0 ) {
v /= i ;
}
}
++ i ;
}
if ( v > 1 ) {
P [ x ] . add ( v );
}
}
}
public boolean canTraverseAllPairs ( int [] nums ) {
int m = Arrays . stream ( nums ). max (). getAsInt ();
int n = nums . length ;
UnionFind uf = new UnionFind ( n + m + 1 );
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j : P [ nums [ i ]] ) {
uf . union ( i , j + n );
}
}
Set < Integer > s = new HashSet <> ();
for ( int i = 0 ; i < n ; ++ i ) {
s . add ( uf . find ( i ));
}
return s . size () == 1 ;
}
}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75 int MX = 100010 ;
vector < int > P [ 100010 ];
int init = []() {
for ( int x = 1 ; x < MX ; ++ x ) {
int v = x ;
int i = 2 ;
while ( i <= v / i ) {
if ( v % i == 0 ) {
P [ x ]. push_back ( i );
while ( v % i == 0 ) {
v /= i ;
}
}
++ i ;
}
if ( v > 1 ) {
P [ x ]. push_back ( v );
}
}
return 0 ;
}();
class UnionFind {
public :
UnionFind ( int n ) {
p = vector < int > ( n );
size = vector < int > ( n , 1 );
iota ( p . begin (), p . end (), 0 );
}
bool unite ( int a , int b ) {
int pa = find ( a ), pb = find ( b );
if ( pa == pb ) {
return false ;
}
if ( size [ pa ] > size [ pb ]) {
p [ pb ] = pa ;
size [ pa ] += size [ pb ];
} else {
p [ pa ] = pb ;
size [ pb ] += size [ pa ];
}
return true ;
}
int find ( int x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
}
private :
vector < int > p , size ;
};
class Solution {
public :
bool canTraverseAllPairs ( vector < int >& nums ) {
int m = * max_element ( nums . begin (), nums . end ());
int n = nums . size ();
UnionFind uf ( m + n + 1 );
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j : P [ nums [ i ]]) {
uf . unite ( i , j + n );
}
}
unordered_set < int > s ;
for ( int i = 0 ; i < n ; ++ i ) {
s . insert ( uf . find ( i ));
}
return s . size () == 1 ;
}
};
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74 const mx = 100010
var p = make ([][] int , mx )
func init () {
for x := 1 ; x < mx ; x ++ {
v := x
i := 2
for i <= v / i {
if v % i == 0 {
p [ x ] = append ( p [ x ], i )
for v % i == 0 {
v /= i
}
}
i ++
}
if v > 1 {
p [ x ] = append ( p [ x ], v )
}
}
}
type unionFind struct {
p , size [] int
}
func newUnionFind ( n int ) * unionFind {
p := make ([] int , n )
size := make ([] int , n )
for i := range p {
p [ i ] = i
size [ i ] = 1
}
return & unionFind { p , size }
}
func ( uf * unionFind ) find ( x int ) int {
if uf . p [ x ] != x {
uf . p [ x ] = uf . find ( uf . p [ x ])
}
return uf . p [ x ]
}
func ( uf * unionFind ) union ( a , b int ) bool {
pa , pb := uf . find ( a ), uf . find ( b )
if pa == pb {
return false
}
if uf . size [ pa ] > uf . size [ pb ] {
uf . p [ pb ] = pa
uf . size [ pa ] += uf . size [ pb ]
} else {
uf . p [ pa ] = pb
uf . size [ pb ] += uf . size [ pa ]
}
return true
}
func canTraverseAllPairs ( nums [] int ) bool {
m := slices . Max ( nums )
n := len ( nums )
uf := newUnionFind ( m + n + 1 )
for i , x := range nums {
for _ , j := range p [ x ] {
uf . union ( i , j + n )
}
}
s := map [ int ] bool {}
for i := 0 ; i < n ; i ++ {
s [ uf . find ( i )] = true
}
return len ( s ) == 1
}
GitHub