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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Greatest Common Divisor Traversal

Number: 2827

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array of integers nums, determine if it is possible to traverse between every pair of indices with a sequence of steps such that for any direct step between indices i and j (i != j), the greatest common divisor (gcd) of nums[i] and nums[j] is greater than 1.

Key Insights

  • The traversal can be modeled as a graph problem where each index is a node.
  • An edge exists between index i and j if gcd(nums[i], nums[j]) > 1.
  • Instead of checking pairwise gcd (which is too slow for large arrays), we can use prime factorization.
  • Connect indices that share a common prime factor through union-find.
  • Efficiently factorize numbers using a precomputed sieve or trial division since maximum nums[i] is 10^5.

Space and Time Complexity

Time Complexity: O(n * log(max(nums[i]))) on average due to factorization and union operations. Space Complexity: O(n + max(nums[i])) for storing union-find structures and prime factor mappings.

Solution

The idea is to view the problem as checking if the induced graph is fully connected. We will:

  1. Factorize each number in the array to get its distinct prime factors.
  2. For every prime factor, link all indices whose numbers contain that factor using a union-find (disjoint set union) data structure.
  3. After processing all numbers, verify that all indices belong to a single connected component.

Data Structures and Approaches:

  • Use an efficient union-find implementation with path compression.
  • Use a dictionary to map a prime factor to the first index encountered for that factor.
  • For each subsequent number containing the same factor, union it with the stored index.

Key Gotchas:

  • Make sure to only consider unique prime factors for each number (avoid duplicate unions).
  • Factorization should be efficient to handle up to 10^5 elements.

Code Solutions

# Python solution using union-find with path compression
import math
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, a):
        # Find with path compression
        if self.parent[a] != a:
            self.parent[a] = self.find(self.parent[a])
        return self.parent[a]
    
    def union(self, a, b):
        # Union the sets by linking their roots
        rootA = self.find(a)
        rootB = self.find(b)
        if rootA != rootB:
            self.parent[rootB] = rootA

def gcd_traversal(nums):
    n = len(nums)
    uf = UnionFind(n)
    # Map prime factor -> first index that contains it
    factor_to_index = {}
    
    # Helper function to get unique prime factors of a number
    def prime_factors(num):
        factors = set()
        # check for factor 2
        while num % 2 == 0:
            factors.add(2)
            num //= 2
        # check for odd factors starting from 3
        f = 3
        while f * f <= num:
            while num % f == 0:
                factors.add(f)
                num //= f
            f += 2
        if num > 1:
            factors.add(num)
        return factors

    # Process each number and union indices sharing any prime factor
    for i, num in enumerate(nums):
        factors = prime_factors(num)
        for factor in factors:
            if factor in factor_to_index:
                uf.union(i, factor_to_index[factor])
            else:
                factor_to_index[factor] = i

    # Check if all indices have the same representative
    root = uf.find(0)
    for i in range(1, n):
        if uf.find(i) != root:
            return False
    return True

# Example usage:
# print(gcd_traversal([2,3,6]))  # Expected output: True
← Back to All Questions