2709. Greatest Common Divisor Traversal

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: Union Find + sieveEratosthenes

• Time complexity: O(Max(nums)log*Max(nums)+nlog*Max(nums))
• Space complexity: O(Max(nums)+n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
const canTraverseAllPairs = function (nums) {
  const n = nums.length;
  const maxNum = Math.max(...nums);

  const sieveEratosthenes = n => {
    const primeFactors = Array.from({ length: n + 1 }, (_, index) => index);

    for (let num = 2; num <= n; num++) {
      if (primeFactors[num] !== num) continue;

      for (let factor = num * num; factor <= n; factor += num) {
        if (primeFactors[factor] === factor) {
          primeFactors[factor] = num;
        }
      }
    }

    return primeFactors;
  };

  const primeFactors = sieveEratosthenes(maxNum);
  const factorMap = new Map();
  const uf = new UnionFind(n);

  const getPrimeFactors = num => {
    const factors = [];

    while (num > 1) {
      const divisor = primeFactors[num];

      factors.push(divisor);

      while (num % divisor === 0) {
        num = Math.floor(num / divisor);
      }
    }

    return factors;
  };

  for (let index = 0; index < n; index++) {
    const num = nums[index];
    const factors = getPrimeFactors(num);

    for (const factor of factors) {
      if (factorMap.has(factor)) {
        uf.union(factorMap.get(factor), index);
      } else {
        factorMap.set(factor, index);
      }
    }
  }

  return uf.maxSize === n;
};

class UnionFind {
  constructor(n) {
    this.groups = Array.from({ length: n }, (_, index) => index);
    this.sizes = Array.from({ length: n }, () => 1);
    this.maxSize = 1;
  }

  find(x) {
    if (this.groups[x] === x) return x;

    this.groups[x] = this.find(this.groups[x]);

    return this.groups[x];
  }

  union(x, y) {
    const groupX = this.find(x);
    const groupY = this.find(y);

    if (groupX === groupY) return false;

    if (this.sizes[groupX] >= this.sizes[groupY]) {
      this.groups[groupY] = groupX;
      this.sizes[groupX] += this.sizes[groupY];
      this.maxSize = Math.max(this.sizes[groupX], this.maxSize);
    } else {
      this.groups[groupX] = groupY;
      this.sizes[groupY] += this.sizes[groupX];
      this.maxSize = Math.max(this.sizes[groupY], this.maxSize);
    }

    return true;
  }
}