We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Greatest Common Divisor Traversal

Difficulty: Hard

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

Key Insights

  • The problem can be modeled as a graph where each index of the array represents a node.
  • An edge exists between two nodes if the gcd of the corresponding values is greater than 1.
  • We need to check if the graph is fully connected, which means there should be a path between any two nodes.
  • A Union-Find (Disjoint Set Union) data structure can be used to efficiently keep track of connected components.

Space and Time Complexity

Time Complexity: O(n * log(max(nums))) where n is the number of elements in the nums array, and max(nums) is the largest element in nums due to the prime factorization that may be needed for each number.

Space Complexity: O(n) for storing the parent and rank arrays used in the Union-Find structure.

Solution

To solve the problem, we can use a Union-Find data structure to manage the connectivity between indices based on their values. The algorithm works as follows:

  1. Iterate over each number and find its prime factors.
  2. For each prime factor, connect the indices of the numbers that share this factor using the Union-Find structure.
  3. After processing all numbers, check if all indices belong to the same connected component by checking their root parents.

This approach allows us to efficiently determine if there is a path between any two indices based on the gcd condition.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

def gcdTraversal(nums):
    from collections import defaultdict
    from math import gcd

    n = len(nums)
    uf = UnionFind(n)
    prime_to_index = defaultdict(list)

    for i in range(n):
        num = nums[i]
        for j in range(2, int(num**0.5) + 1):
            if num % j == 0:
                prime_to_index[j].append(i)
                while num % j == 0:
                    num //= j
        if num > 1:  # num is prime
            prime_to_index[num].append(i)

    for indices in prime_to_index.values():
        for i in range(1, len(indices)):
            uf.union(indices[0], indices[i])

    root = uf.find(0)
    for i in range(1, n):
        if uf.find(i) != root:
            return False
    return True
← Back to All Questions