How hard is LeetCode 2709. Greatest Common Divisor Traversal?

LeetCode 2709. Greatest Common Divisor Traversal is rated Hard on LeetCode.

What is the time complexity of LeetCode 2709. Greatest Common Divisor Traversal?

The Python solution on this page runs in Near O(n) (amortized).

What is the space complexity of LeetCode 2709. Greatest Common Divisor Traversal?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2709. Greatest Common Divisor Traversal cover?

LeetCode 2709. Greatest Common Divisor Traversal is tagged Union Find, Array, Math and Number Theory on LeetCode.

Greatest Common Divisor Traversal — LeetCode 2709 Python Solution

HardUnion FindArrayMathNumber Theory

Problem: #2709
Pattern: Union-Find
Reading time: 9 min
Source: leetcode.com

The problem

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.

Example

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).

Python solution

Python

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

Complexity

Measure	Complexity
Time	Near O(n) (amortized)
Space	O(n) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2709. Greatest Common Divisor Traversal is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Union Find.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2709. Greatest Common Divisor Traversal?: LeetCode 2709. Greatest Common Divisor Traversal is rated Hard on LeetCode.
What is the time complexity of LeetCode 2709. Greatest Common Divisor Traversal?: The Python solution on this page runs in Near O(n) (amortized).
What is the space complexity of LeetCode 2709. Greatest Common Divisor Traversal?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2709. Greatest Common Divisor Traversal cover?: LeetCode 2709. Greatest Common Divisor Traversal is tagged Union Find, Array, Math and Number Theory on LeetCode.