Greatest Common Divisor Traversal Interview Question for Google

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.

import math

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

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])  # Path compression
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self.rank[root_i] < self.rank[root_j]:
                self.parent[root_i] = root_j
            elif self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            else:
                self.parent[root_j] = root_i
                self.rank[root_i] += 1

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def canTraverseAllPairs(nums):
    n = len(nums)
    if n == 1:
        return True

    uf = UnionFind(n)

    for i in range(n):
        for j in range(i + 1, n):
            if gcd(nums[i], nums[j]) > 1:
                uf.union(i, j)

    # Check if all elements are in the same connected component
    root = uf.find(0)
    for i in range(1, n):
        if uf.find(i) != root:
            return False

    return True

# Optimized solution with prime factorization
def canTraverseAllPairsOptimized(nums):
    n = len(nums)
    if n == 1:
        return True

    uf = UnionFind(n)
    prime_to_index = {}

    def prime_factors(num):
        factors = set()
        d = 2
        while d * d <= num:
            while num % d == 0:
                factors.add(d)
                num //= d
            d += 1
        if num > 1:
            factors.add(num)
        return factors

    for i in range(n):
        factors = prime_factors(nums[i])
        for factor in factors:
            if factor in prime_to_index:
                uf.union(i, prime_to_index[factor])
            else:
                prime_to_index[factor] = i

    root = uf.find(0)
    for i in range(1, n):
        if uf.find(i) != root:
            return False

    return True

# Example Usages:
nums1 = [2, 3, 6]
print(f"Input: {nums1}, Output: {canTraverseAllPairsOptimized(nums1)}")  # Output: True

nums2 = [3, 9, 5]
print(f"Input: {nums2}, Output: {canTraverseAllPairsOptimized(nums2)}")  # Output: False

nums3 = [4, 3, 12, 8]
print(f"Input: {nums3}, Output: {canTraverseAllPairsOptimized(nums3)}")  # Output: True

nums4 = [1, 15, 7, 8, 20]
print(f"Input: {nums4}, Output: {canTraverseAllPairsOptimized(nums4)}") # Output: True

nums5 = [1,2,3]
print(f"Input: {nums5}, Output: {canTraverseAllPairsOptimized(nums5)}") # Output: false

Brute Force Solution

The brute force approach involves iterating through all pairs of indices (i, j) and checking if there exists a path between them. This can be done using Depth-First Search (DFS) or Breadth-First Search (BFS). The time complexity for this approach is high because for each pair, we potentially have to explore all possible paths.

Optimal Solution

The optimized solution uses the Union-Find data structure combined with prime factorization. Here's a breakdown:

Prime Factorization: For each number in nums, find its prime factors.
Union-Find: Use Union-Find to connect indices that share a common prime factor. This means if nums[i] and nums[j] share a prime factor, we union indices i and j.
Connectivity Check: After processing all numbers, check if all indices are connected (i.e., belong to the same connected component) using the Union-Find data structure. If they are, it's possible to traverse between all pairs.

Big(O) Run-time Analysis

Prime Factorization: Factoring a number n takes O(sqrt(n)) time in the worst case.
Union-Find: The Union-Find operations (find and union) take nearly constant time on average, close to O(α(n)), where α(n) is the inverse Ackermann function, which grows extremely slowly. For all practical input sizes, α(n) can be considered to be less than 5.
Overall: The dominant factor is the prime factorization step, which is performed for each number in the input array. Therefore, the overall time complexity is O(n * sqrt(max(nums))), where n is the length of the nums array and max(nums) is the maximum value in the nums array.

Big(O) Space Usage Analysis

Union-Find: The Union-Find data structure uses O(n) space to store the parent and rank arrays, where n is the number of elements in the input array.
Prime Factorization: The prime factorization process requires storing prime factors, which in the worst case can take O(log(max(nums))) space per number.
Overall: The overall space complexity is O(n), dominated by the Union-Find data structure.

Edge Cases and Handling

Empty Input: If the input array is empty, it's not possible to traverse between any pairs, so return False.
Single Element: If the input array contains only one element, it's trivially possible to traverse, so return True.
Numbers with GCD of 1: If there are numbers in the array that have a GCD of 1, ensure the algorithm correctly identifies if all pairs can still be traversed.
Large Prime Numbers: Handling large prime numbers efficiently during factorization is important to avoid performance bottlenecks.
Numbers equal to 1: If any number is 1, then it won't have any common factor with any other number (except 1 itself). If we have multiple such '1's, they should ideally form a connected component, otherwise it's impossible to traverse between all pairs.